Graphs with odd and even distances between non-cut vertices
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 w...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AGH Univeristy of Science and Technology Press
2024-12-01
|
| Series: | Opuscula Mathematica |
| Subjects: | |
| Online Access: | https://www.opuscula.agh.edu.pl/vol45/1/art/opuscula_math_4501.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1232-9274 |