论文标题
在环形分解式式票形图中，哈密顿循环图
Hamiltonian cycles in annular decomposable Barnette graphs
论文作者
论文摘要
Barnette的猜想是图理论中未解决的问题。该问题指出，每3个常规（立方），三个连接，平面，两部分（Barnette）图是汉密尔顿的。部分结果是对顶点数量的限制，面部分区的几个属性和双向图的双图，而某些研究仅着眼于Barnette图的结构表征。指出蜘蛛网图是环形可分解的巴内特（ADB图）图的一个子类，并且是哈密顿量，我们研究了ADB图及其环形连接子类（ADB-AC图）。我们表明，可以使用递归边缘操作从最小的Barnette图生成ADB-AC图。我们得出了几种条件，可确保在ADB-AC图中存在Hamiltonian周期，而不会对面部分区的顶点，面部大小或任何其他约束施加限制。我们表明，ADB-AC图中可以有两种类型的Annuli，Ring Annuli和Block Annuli。我们的主要结果是，具有无环的Andull序列的ADB-AC图是哈密顿量。
Barnette's conjecture is an unsolved problem in graph theory. The problem states that every 3-regular (cubic), 3-connected, planar, bipartite (Barnette) graph is Hamiltonian. Partial results have been derived with restrictions on number of vertices, several properties of face-partitions and dual graphs of Barnette graphs while some studies focus just on structural characterizations of Barnette graphs. Noting that Spider web graphs are a subclass of Annular Decomposable Barnette (ADB graphs) graphs and are Hamiltonian, we study ADB graphs and their annular-connected subclass (ADB-AC graphs). We show that ADB-AC graphs can be generated from the smallest Barnette graph using recursive edge operations. We derive several conditions assuring the existence of Hamiltonian cycles in ADB-AC graphs without imposing restrictions on number of vertices, face size or any other constraints on the face partitions. We show that there can be two types of annuli in ADB-AC graphs, ring annuli and block annuli. Our main result is, ADB-AC graphs having non singular sequences of ring annuli are Hamiltonian.
