论文标题
$ \ frac {3} {2} $的构造 - 坚硬的平面三角剖分，没有2因子
A construction of a $\frac{3}{2}$-tough plane triangulation with no 2-factor
论文作者
论文摘要
1956年，图特证明了著名的定理，每个4个连接的平面图都是哈密顿式的。该结果意味着，每至少三个顶点上的艰难平面图都是哈密顿式的，因此有一个2因子。欧文斯（Owens）在1999年构建了韧性的非汉顿最大平面图，任意接近$ \ frac {3} {2} $，并询问是否存在最大的非汉顿平面图形韧性的最大平面图$ \ frac {3} {2} {2} $。实际上，构造的欧文斯的图甚至不包含2因子。因此，恰好$ \ frac {3} {2} $的韧性是询问在坚硬平面图中存在2因子的唯一情况。鲍尔（Bauer），布罗斯玛（Broersma）和施梅切尔（Schmeichel）在一项调查中也提出了这个问题。在本文中，我们通过构建一个最大$ \ frac {3} {2} $ - 坚硬的平面图，没有2因子，回答了欧文斯以及鲍尔，布罗斯玛和schmeichel的问题。
In 1956, Tutte proved the celebrated theorem that every 4-connected planar graph is hamiltonian. This result implies that every more than $\frac{3}{2}$-tough planar graph on at least three vertices is hamiltonian and so has a 2-factor. Owens in 1999 constructed non-hamiltonian maximal planar graphs of toughness arbitrarily close to $\frac{3}{2}$ and asked whether there exists a maximal non-hamiltonian planar graph of toughness exactly $\frac{3}{2}$. In fact, the graphs Owens constructed do not even contain a 2-factor. Thus the toughness of exactly $\frac{3}{2}$ is the only case left in asking the existence of 2-factors in tough planar graphs. This question was also asked by Bauer, Broersma, and Schmeichel in a survey. In this paper, we close this gap by constructing a maximal $\frac{3}{2}$-tough plane graph with no 2-factor, answering the question asked by Owens as well as by Bauer, Broersma, and Schmeichel.
