**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.