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.
翻译:Barnette 的猜想称, 所有的立方、 3个连接、 平面、 双方图都是汉密尔顿式的。 我们将这一猜想转换为匹配的理论设置。 这让我们可以放松对准的假设要求, 给所有立方、 3个连接、 Pfaffian 、 双方图都是汉密尔顿式的等同假设。 除了长度三的路径外, 图表是一个支撑, 如果它是双向的, 任何两个脱节边缘都是完美匹配的一部分 。 我们的视角允许我们观察 巴内特 的预测可以降为立方、 平面牙套。 我们显示对立方、 3个连接、 双方图的类似减幅, 以显示四个更强的汉密尔顿性版本。 注意在这些情况下我们不需要计划。 作为这些结果的实用应用, 我们为Holton 等人 发现的一个立方、 3个连接、 平面、 双方图是完美匹配的代程序提供了一些补充。 [ 汉顿 周期的周期可以让我们选择1985年的双方平面图。