论文标题
一个或两个顶点度的图表中的哈密顿周期很少
Few hamiltonian cycles in graphs with one or two vertex degrees
论文作者
论文摘要
我们完全反驳了Haythorpe在常规汉密尔顿图中的最小汉密尔顿周期数量上的猜想，从而扩大了Zamfirescu的结果，以及正确和补充Haythorpe的计算结果。数学。 27（2018）426-430]。此后，我们使用Lovász局部引理扩展了Thomassen的独立主导套装方法。关于这种方法的局限性，我们回答了Haxell，Seamone和Verstraete的问题，并解决了Thomassen问题的第一个开放式案例。通过观察Aldred和Thomassen的动机，我们证明，对于\ {2，3 \} $中的每个$κ\，以及任何积极的整数$ k $，都有许多无限的连接性$κ$的图形$κ$包含一个汉密尔顿周期，并且每个角色都有一个$ 3 $或$ 2K $ 2K $。
We fully disprove a conjecture of Haythorpe on the minimum number of hamiltonian cycles in regular hamiltonian graphs, thereby extending a result of Zamfirescu, as well as correct and complement Haythorpe's computational enumerative results from [Experim. Math. 27 (2018) 426-430]. Thereafter, we use the Lovász Local Lemma to extend Thomassen's independent dominating set method. Regarding the limitations of this method, we answer a question of Haxell, Seamone, and Verstraete, and settle the first open case of a problem of Thomassen. Motivated by an observation of Aldred and Thomassen, we prove that for every $κ\in \{ 2, 3 \}$ and any positive integer $k$, there are infinitely many non-regular graphs of connectivity $κ$ containing exactly one hamiltonian cycle and in which every vertex has degree $3$ or $2k$.
