论文标题
债券在$ k $连接的图中与长路相交
Bonds intersecting long paths in $k$-connected graphs
论文作者
论文摘要
加赖（Gallai）（1966）的一个著名问题问，是否有一个顶点穿过连接图的所有最长路径。尽管已经对某些特殊类别的图表进行了验证，例如外平面图，圆形弧形图和串联平行图，但答案对一般图是负面的。在本文中，我们证明，如果我们用债券替换顶点，那么答案是肯定的。图的键是最小的非空边距。特别是，在任何2个连接的图中，入射到顶点的所有边缘的集合都是键，称为顶点键。显然，对于2个连接的图，一条路径通过顶点$ v $，并且仅当它相对于$ v $符合顶点键。因此，加赖问题的一种非常自然的方法是研究是否有债券满足所有最长的途径。令$ p $表示连接图的最长路径的长度。我们表明，对于任何2个连接的图，都有一个债券满足所有长度至少$ p-1 $的债券。然后，我们证明，对于任何3个连接的图，都有一个债券满足所有长度至少$ P-2 $的路径。对于$ k $连接的图形$（k \ ge3）$，我们表明，有一个债券满足所有长度至少$ p-t+1 $的债券，其中$ t = \ big \ lfloor \ sqrt \ sqrt {\ frac {k-2} $ t = \ big \ lceil \ sqrt {\ frac {k-2} {2}}} \ big big \ rceil $如果$ p $是奇数的。我们的结果提供了P. Wu和S. mcguinness的相应结果的类似物[键在图中相交的循环，Combinatorica 25（4）（2005），439-450]。
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\ge3)$, we show that there is a bond meeting all paths of length at least $p-t+1$, where $t=\Big\lfloor\sqrt{\frac{k-2}{2}}\Big\rfloor$ if $p$ is even and $t=\Big\lceil\sqrt{\frac{k-2}{2}}\Big\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.
