Bonds Intersecting Long Paths in \(k\) -Connected Graphs
Qinghong Zhao, Bing Wei, Haidong Wu · SIAM Journal on Discrete Mathematics · 2023
Abstract. In 1966, Gallai asked whether there is a vertex which passes through all longest paths of a connected graph. Although this has been verified for some special classes of graphs such as outerplanar graphs, circular arc graphs, and series-parallel graphs, the answer is negative for general graphs. In this paper, we prove among other results that if we replace the vertex by a bond, then the answer is affirmative. A bond of a graph is a minimal nonempty edge-cut. In particular, in any 2-connected graph, the set of all edges incident to a vertex is a bond, called a vertex-bond. Clearly, for a 2-connected graph, a path passes through a vertex [Formula: see text] if and only if it meets the vertex-bond with respect to [Formula: see text]. Therefore, a very natural approach to Gallai’s question is to study whether there is a bond meeting all longest paths. Let [Formula: see text] denote the length of a longest path of connected graphs. We show that there is a bond meeting all paths of length at least [Formula: see text] and [Formula: see text] for any 2- and 3-connected graph, respectively. For any [Formula: see text]-connected graph [Formula: see text], we show that there is a bond meeting all paths of length at least [Formula: see text], where [Formula: see text] if [Formula: see text] is even and [Formula: see text] if [Formula: see text] is odd. Our results also provide analogs of the results on bonds meeting long cycles given in [P.-L. Wu, Combin. Probab. Comput., 6 (1997), pp. 107–113; and S. McGuinness, Combinatorica, 25 (2005), pp. 439–450].