Graphs with odd and even distances between non-cut vertices

• Autorzy: Antoshyna Kateryna , Kozerenko Sergiy

Identyfikatory

DOI

10.7494/OpMath.2025.45.1.5

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

non-cut vertex; graph distance; line graph; block; strong unique independence tree

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 1
• Strony: 5--25
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Antoshyna Kateryna

• Institute of Mathematics of the National Academy of Sciences of Ukraine, 01024 Kyiv, Ukraine

• https://orcid.org/0009-0005-9221-1351

autor

Kozerenko Sergiy

• Department of Mathematics, National University of Kyiv-Mohyla Academy, 04070 Kyiv, Ukraine
• Kyiv School of Economics, 03113 Kyiv, Ukraine

• https://orcid.org/0000-0002-5716-3084

Bibliografia

• [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] 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.
• [3] A.W. Dress, R. Scharlau, Gated sets in metric spaces, Aequationes Math. 34 (1987), 112–120.
• [4] I. Gelbukh, Criterion for a graph to admit a good orientation in terms of leaf blocks, Monatsh. Math. 198 (2022), 61–77.
• [5] F. Harary, A characterization of block graphs, Canad. Math. Bull. 6 (1963), 1–6.
• [6] F. Harary, Graph Theory, Addison-Wesley Publishing Company, Boston, 1969.
• [7] G. Hopkins, W. Staton, Graphs with unique maximum independent sets, Discrete Math. 57 (1985), 245–251.
• [8] D.C. Kay, G. Chartrand, A characterization of certain ptolemaic graphs, Canad. J. Math. 17 (1965), 342–346.
• [9] V.V. Sharko, About Kronrod–Reeb graph of a function on a manifold, Methods Funct. Anal. Topology 12 (2006), 389–396.
• [10] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150–168.