Detour trees

作者：Jobson Adam S; Kezdy Andre E^*; Lehel Jeno; White Susan C

来源：Discrete Applied Mathematics, 2016, 206: 73-80.

DOI：10.1016/j.dam.2016.02.002

• Intersecting longest paths
• Intersecting longest cycles
• Dually chordal graphs
• Helly property
• Compatible trees
• Cographs

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.

• 出版日期2016-6-19