Hitting All Longest Paths

Originator(s): Jenö Lehel, Tudor Zamfirescu

Definition: Let the path-transversal number of a graph be the minimum number of vertices needed to have a vertex of every maximum-length path.

Question 1: (Lehel) Does every connected chordal graph have path-transversal number 1?

Question 2: (Zamfirescu) What is the largest q such that in every connected graph, every set of q longest paths have a common vertex?

Background: T. Gallai asked in 1966 whether every connected graph has a vertex that appears in all longest paths. Zamfirescu [1976] found a counterexample with 12 vertices. It is not known whether one can construct connected graphs with arbitrarily large path-transversal number. For related problems, see Voss [V].

Partial results: All graphs in this discussion are required to be connected. It is immediate that every tree has path-tranversal number 1, since all longest paths contain the center. Klavzar and Petkovsek [KP] proved that if every block of G is Hamiltonian-connected (every two vertices are the endpoints of some spanning path), then G has path-transversal number 1. Thus block graphs have path-transversal number 1, and it is also easy to prove this for split graphs. For interval graphs it was proved by Balister, Gyori, Lehel, and Schelp [BGLS], along with the more general result that circular arc graphs have path transversal number 1.

For Question 2, it is well-known that every two longest paths in a connected graph have a common vertex. Skupien [S] obtained, for k >= 7, a connected graph in which some k longest paths have no common vertex, but every k-1 longest paths have a common vertex. It is not known whether every three maximum-length paths in a connected graph have a common vertex, so the value of q in Question 2 is at least 2 and at most 6.

References:
[BGLS] Balister, P.; Gyori, E.; Lehel, J.; Schelp, R. Longest paths in circular arc graphs. J. Combin. Prob. Comput., to appear.
[KP] Klav\v{z}ar, S.; Petkov\v{s}ek, M. Graphs with nonempty intersection of longest paths, Ars Combin. 29 (1990) 43--52.
[S] Skupie\'n, Z. Smallest sets of longest paths with empty intersection. Combin. Probab. Comput. 5 (1996), no. 4, 429--436.
[V] Voss, H.-J. {\em Cycles and bridges in graphs}, Mathematics and its Applications (East European Series), 49. Kluwer Academic Publishers Group, Dordrecht; VEB Deutscher Verlag der Wissenschaften, Berlin, 1991.
[Z] Zamfirescu, T. On longest paths and circuits in graphs. Math. Scand. 38 (1976), no. 2, 211--239.

Back to Index Page Link to Glossary