Bibliographic Details
| Title: |
Detour trees. |
| Authors: |
Jobson, Adam S.1, Kézdy, André E.1 kezdy@louisville.edu, Lehel, Jenő1, White, Susan C.2 |
| Source: |
Discrete Applied Mathematics. Jun2016, Vol. 206, p73-80. 8p. |
| Subjects: |
Tree graphs, Length measurement, Geometric vertices, Graph connectivity, Paths & cycles in graph theory |
| Abstract: |
A detour of a graph is a path of maximum length. A vertex that is common to all detours of a graph is called a Gallai vertex . As a tool to prove the existence of a Gallai vertex, we introduce the concept of a detour tree , a spanning tree of a graph in which the vertex set of any detour of the graph induces a subtree. We give several characterizations of graphs that have a detour tree. We also prove that any compatible tree of a connected dually chordal graph is a detour tree. This, combined with the fact that subtrees of a tree satisfy the Helly property, guarantees that every connected dually chordal graph contains at least one Gallai vertex. Consequently, connected graphs from subfamilies of dually chordal graphs have a Gallai vertex, including the well-studied doubly chordal, strongly chordal and interval graphs. Separately we prove that connected cographs (which are not necessarily dually chordal) have a Gallai vertex. Analogous results for cycles of maximum length follow. [ABSTRACT FROM AUTHOR] |
|
Copyright of Discrete Applied Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
