论文标题
5型图中的哈密顿周期和1因子
Hamiltonian cycles and 1-factors in 5-regular graphs
论文作者
论文摘要
事实证明，对于任何整数$ g \ ge 0 $和$ k \ in \ {0，\ ldots，10 \} $，存在着无限的许多5个属属$ g $的图形，其中包含1件量的属性，具有$ k $ k $ k $ k $ p的1因子，即完美的。对于$ g = 0 $，这解决了1964年的Kotzig问题。由Kotzig和Labelle的“婚姻”操作激励，我们讨论了两种旨在产生高环状边缘连接图的胶合技术。我们证明，存在无限的许多平面5与5型图的图形，其中每个1次分子化的完美对零。另一方面，由四种颜色定理和Brinkmann和第一作者的结果，每个平面4与5个型号的图形满足了其在哈密顿周期上的条件的条件具有线性数量的1个因子，每个都包含至少一个完美的一对。我们还证明，满足较强条件的每个平面5与5台式图都包含一个1次分子化，最多九个完美对，因此，每个这样的图形都承认具有十对完美的1次分子化，至少具有两个边缘 - kempe等效类。本文结束了在平面5型图中的边缘 - 凯姆佩当量类别的进一步结果。
It is proven that for any integer $g \ge 0$ and $k \in \{ 0, \ldots, 10 \}$, there exist infinitely many 5-regular graphs of genus $g$ containing a 1-factorisation with exactly $k$ pairs of 1-factors that are perfect, i.e. form a hamiltonian cycle. For $g = 0$, this settles a problem of Kotzig from 1964. Motivated by Kotzig and Labelle's "marriage" operation, we discuss two gluing techniques aimed at producing graphs of high cyclic edge-connectivity. We prove that there exist infinitely many planar 5-connected 5-regular graphs in which every 1-factorisation has zero perfect pairs. On the other hand, by the Four Colour Theorem and a result of Brinkmann and the first author, every planar 4-connected 5-regular graph satisfying a condition on its hamiltonian cycles has a linear number of 1-factorisations each containing at least one perfect pair. We also prove that every planar 5-connected 5-regular graph satisfying a stronger condition contains a 1-factorisation with at most nine perfect pairs, whence, every such graph admitting a 1-factorisation with ten perfect pairs has at least two edge-Kempe equivalence classes. The paper concludes with further results on edge-Kempe equivalence classes in planar 5-regular graphs.
