Opuscula Math. 45, no. 1 (2025), 5-25
https://doi.org/10.7494/OpMath.2025.45.1.5
Opuscula Mathematica
Graphs with odd and even distances between non-cut vertices
Kateryna Antoshyna
Sergiy Kozerenko
Abstract. We prove that in a connected graph, the distances between non-cut vertices are odd if and only if it is the line graph of a strong unique independence tree. We then show that any such tree can be inductively constructed from stars using a simple operation. Further, we study the connected graphs in which the distances between non-cut vertices are even (shortly, NCE-graphs). Our main results on NCE-graphs are the following: we give a criterion of NCE-graphs, show that any bipartite graph is an induced subgraph of an NCE-graph, characterize NCE-graphs with exactly two leaves, characterize graphs that can be subdivided to NCE-graphs, and provide a characterization for NCE-graphs which are maximal with respect to the edge addition operation.
Keywords: non-cut vertex, graph distance, line graph, block, strong unique independence tree.
Mathematics Subject Classification: 05C12, 05C05, 05C75.
- K. Antoshyna, S. Kozerenko, Graphs with parity conditions between non-cut vertices, International Conference of Young Mathematicians, June 1-3, 2023, Kyiv, Ukraine.
- H.-J. Bandelt, V. Chepoi, Metric graph theory and geometry: a survey, from "Surveys on discrete and computational geometry" (J. E. Goodman, J. Pach, R. Pollack, editors), Contemp. Math. 453, Amer. Math. Soc. (2008), 49-86. https://doi.org/10.1090/conm/453/08795
- A.W. Dress, R. Scharlau, Gated sets in metric spaces, Aequationes Math. 34 (1987), 112-120. https://doi.org/10.1007/bf01840131
- I. Gelbukh, Criterion for a graph to admit a good orientation in terms of leaf blocks, Monatsh. Math. 198 (2022), 61-77. https://doi.org/10.1007/s00605-022-01681-6
- F. Harary, A characterization of block graphs, Canad. Math. Bull. 6 (1963), 1-6. https://doi.org/10.4153/cmb-1963-001-x
- F. Harary, Graph Theory, Addison-Wesley Publishing Company, Boston, 1969.
- G. Hopkins, W. Staton, Graphs with unique maximum independent sets, Discrete Math. 57 (1985), 245-251. https://doi.org/10.1016/0012-365x(85)90177-3
- D.C. Kay, G. Chartrand, A characterization of certain ptolemaic graphs, Canad. J. Math. 17 (1965), 342-346. https://doi.org/10.4153/cjm-1965-034-0
- V.V. Sharko, About Kronrod-Reeb graph of a function on a manifold, Methods Funct. Anal. Topology 12 (2006), 389-396.
- H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150-168. https://doi.org/10.2307/2371086
- Kateryna Antoshyna
https://orcid.org/0009-0005-9221-1351- Institute of Mathematics of the National Academy of Sciences of Ukraine, 01024 Kyiv, Ukraine
- Sergiy Kozerenko (corresponding author)
- https://orcid.org/0000-0002-5716-3084
- Department of Mathematics, National University of Kyiv-Mohyla Academy, 04070 Kyiv, Ukraine
- Kyiv School of Economics, 03113 Kyiv, Ukraine
- Communicated by Dalibor Fronček.
- Received: 2023-07-26.
- Revised: 2024-11-05.
- Accepted: 2024-11-12.
- Published online: 2024-12-20.
