2022/01/27 by Bing Wei, Haidong Wu, Wei, Bing +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.2201.11245
17 pages, 15 figures
arxiv created 2022/01/27 · arxiv updated 2022/01/28
A well-known question of Gallai (1966) 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 v if and only if it meets the vertex-bond with respect to v. Therefore, a very natural approach to Gallai's question is to study whether there is a bond meeting all longest paths. Let p denote the length of a longest path of connected graphs. We show that for any 2-connected graph, there is a bond meeting all paths of length at least p-1. We then prove that for any 3-connected graph, there is a bond meeting all paths of length at least p-2. For a k-connected graph (k≥3), we show that there is a bond meeting all paths of length at least p-t+1, where t=\lfloor√((k-2)/(2))\rfloor if p is even and t=\lceil√((k-2)/(2))\rceil if p is odd. Our results provide analogs of the corresponding results of P. Wu and S. McGuinness [Bonds intersecting cycles in a graph, Combinatorica 25 (4) (2005), 439-450] also.