论文标题
匹配理论和巴内特的猜想
Matching Theory and Barnette's Conjecture
论文作者
论文摘要
Barnette的猜想声称所有立方，三个连接的，平面，两分图都是哈密顿式的。我们将此猜想的翻译转换为匹配理论环境。这使我们能够放宽平面性的要求，以给出同等的猜想，即所有三次，三个连接的，pfaffian，两部分图都是哈密顿式的。 如果长度三的路径除外，则图形是括号，如果它是双分部分，并且任何两个脱节边缘都是完美匹配的一部分。我们的观点使我们可以观察到巴内特的猜想可以减少到立方的平面牙套。我们显示出与三种较强版本的hamiltonicity的三次连接的两分图的牙套相似的减少。请注意，在这些情况下，我们不需要平面。作为这些结果的实际应用，我们为Holton等人发现的分数，三个连接，平面，二分图的生成程序提供了一些补充。 [Cubic 3连接的两部分平面图中的Hamiltonian循环，JCTB，1985年]。这些使我们能够检查我们生成的图是否是支撑。
Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. This allows us to relax the requirement of planarity to give the equivalent conjecture that all cubic, 3-connected, Pfaffian, bipartite graphs are Hamiltonian. A graph, other than the path of length three, is a brace if it is bipartite and any two disjoint edges are part of a perfect matching. Our perspective allows us to observe that Barnette's Conjecture can be reduced to cubic, planar braces. We show a similar reduction to braces for cubic, 3-connected, bipartite graphs regarding four stronger versions of Hamiltonicity. Note that in these cases we do not need planarity. As a practical application of these results, we provide some supplements to a generation procedure for cubic, 3-connected, planar, bipartite graphs discovered by Holton et al. [Hamiltonian Cycles in Cubic 3-Connected Bipartite Planar Graphs, JCTB, 1985]. These allow us to check whether a graph we generated is a brace.
