On a Conjecture Concerning the Petersen Graph
On a Conjecture Concerning the Petersen Graph
复制标题
关于Petersen图的一个猜想
DOI：
--
复制
发表时间：
2011
影响因子：
0.7
通讯作者：
X. Zha
中科院分区：
文献类型：
--
作者：
Donald Nelson;M. Plummer;N. Robertson;X. Zha
Robertson推测，周长为5且每个长度大于5的奇环都有弦的唯一的3连通内4连通图是Petersen图。我们在同样是三次图的特殊情况下证明了这个猜想。而且，这个证明不需要内部4连通性假设。然后给出了一个例子，表明内部4连通性的假设不能作为原始猜想中的假设而被丢弃。然后，我们总结了我们的结果，旨在解决猜想的原始形式。特别地，设$G$为任意周长为5的3连通内4连通图，其中每个长度大于5的奇环都有一个弦。如果$C$是$G$中的任意周长循环，则$N(C)ackslash V(C)$不可能是无边的，并且如果$N(C)ackslash V(C)$包含长度至少为2的路径，则该猜想为真。因此，如果猜想为假并且$H$是反例，则对于$H$中的任意周长周期$C$, $N(C) ackslash V(C)$诱导出一个非平凡匹配$M$以及一组独立的顶点。此外，$M$可以划分为（最多）两个不相交的非空集，我们可以精确地描述这些集是如何附着在循环$C$上的。
Robertson has conjectured that the only 3-connected internally 4-connected graph of girth 5 in which every odd cycle of length greater than 5 has a chord is the Petersen graph. We prove this conjecture in the special case where the graphs involved are also cubic. Moreover, this proof does not require the internal-4-connectivity assumption. An example is then presented to show that the assumption of internal 4-connectivity cannot be dropped as an hypothesis in the original conjecture. We then summarize our results aimed toward the solution of the conjecture in its original form. In particular, let $G$ be any 3-connected internally-4-connected graph of girth 5 in which every odd cycle of length greater than 5 has a chord. If $C$ is any girth cycle in $G$ then $N(C)ackslash V(C)$ cannot be edgeless, and if $N(C) ackslash V(C)$ contains a path of length at least 2, then the conjecture is true. Consequently, if the conjecture is false and $H$ is a counterexample, then for any girth cycle $C$ in $H$, $N(C) ackslash V(C)$ induces a nontrivial matching $M$ together with an independent set of vertices. Moreover, $M$ can be partitioned into (at most) two disjoint non-empty sets where we can precisely describe how these sets are attached to cycle $C$.