Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in-tournaments
Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in-tournaments
复制标题
DOI：
10.1002/jgt.v60:2
复制
发表时间：
2009-02
影响因子：
0.9
通讯作者：
Rong Luo;L. Miao;Yue Zhao
中科院分区：
文献类型：
--
作者：
Rong Luo;L. Miao;Yue Zhao
比赛中是一个有向图，使得每个顶点的负邻域都引起比赛。设m = 4或m = 5，并设D是阶为${{n}}\geq {{2}}{{m}}-{{2}}$的强连通竞赛，使得每个弧都属于至少阶为m的有向路径。在2000年，Volkmann证明，如果D包含一个弧e，使得通过e的最长有向路径恰好由m个顶点组成，那么e是D中唯一具有该性质的弧。在这篇文章中，我们将看到这个命题对于${{m}}\geq {{4}}$是正确的，从而证实了Volkmann的一个猜想。进一步，我们证明了如果我们将D的顺序限制放宽到${{n}}\geq {{2}}{{m}}-{{3}}$，所讨论的比赛中的D最多有两个这样的弧。在此过程中，我们也会用两条这样的弧线来描述比赛中的特征。©2008 Wiley期刊公司[J] .图论学报（自然科学版），2009
An in-tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let m = 4 or m = 5 and let D be a strongly connected in-tournament of order ${{n}}\geq {{2}}{{m}}-{{2}}$ such that each arc belongs to a directed path of order at least m. In 2000, Volkmann showed that if D contains an arc e such that the longest directed path through e consists of exactly m vertices, then e is the only arc of D with that property. In this article we shall see that this proposition is true for ${{m}}\geq {{4}}$, thereby validating a conjecture of Volkmann. Furthermore, we prove that if we ease the restrictions on the order of D to ${{n}}\geq {{2}}{{m}}-{{3}}$, the in-tournament D in question has at most two such arcs. In doing so, we also give a characterization of the in-tournaments with exactly two such arcs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 130–148, 2009