Opuscula Mathematica
Opuscula Math. 45, no. 1 (2025), 5-25

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.
Full text (pdf)
References ▼
  1. [1] K. Antoshyna, S. Kozerenko, Graphs with parity conditions between non-cut vertices, International Conference of Young Mathematicians, June 1-3, 2023, Kyiv, Ukraine.
  2. [2] 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
  3. [3] A.W. Dress, R. Scharlau, Gated sets in metric spaces, Aequationes Math. 34 (1987), 112-120. https://doi.org/10.1007/bf01840131
  4. [4] 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
  5. [5] F. Harary, A characterization of block graphs, Canad. Math. Bull. 6 (1963), 1-6. https://doi.org/10.4153/cmb-1963-001-x
  6. [6] F. Harary, Graph Theory, Addison-Wesley Publishing Company, Boston, 1969.
  7. [7] 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
  8. [8] 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
  9. [9] V.V. Sharko, About Kronrod-Reeb graph of a function on a manifold, Methods Funct. Anal. Topology 12 (2006), 389-396.
  10. [10] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150-168. https://doi.org/10.2307/2371086
About the authors ▼
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
About the article ▼
Communicated by Dalibor Fronček.
Received: 2023-07-26.
Revised: 2024-11-05.
Accepted: 2024-11-12.
Published online: 2024-12-20.
Cite this article as ▼
Kateryna Antoshyna, Sergiy Kozerenko, Graphs with odd and even distances between non-cut vertices, Opuscula Math. 45, no. 1 (2025), 5-25, https://doi.org/10.7494/OpMath.2025.45.1.5.
Download this article's citation as: