Non-hamiltonian graphs in which every edge-contracted subgraph is hamiltonian
作者：
Highlights：
• We introduce and investigate perihamiltonian graphs, a generalisation of hypohamiltonian graphs.
• We use a recent result of Wiener to show that there are infinitely many perihamiltonian graphs of connectivity k for any k ≥ 2.
• We strengthen a theorem of Thomassen by proving that every planar perihamiltonian graph of connectivity k contains a vertex of degree k.
• Thus, if in a polyhedral graph of minimum degree at least 4 the set of vertices whose removal yields a non-hamiltonian graph is independent, the graph itself must be hamiltonian.
• We prove that there are infinitely many polyhedral perihamiltonian graphs containing no adjacent cubic vertices.
摘要
•We introduce and investigate perihamiltonian graphs, a generalisation of hypohamiltonian graphs.•We use a recent result of Wiener to show that there are infinitely many perihamiltonian graphs of connectivity k for any k ≥ 2.•We strengthen a theorem of Thomassen by proving that every planar perihamiltonian graph of connectivity k contains a vertex of degree k.•Thus, if in a polyhedral graph of minimum degree at least 4 the set of vertices whose removal yields a non-hamiltonian graph is independent, the graph itself must be hamiltonian.•We prove that there are infinitely many polyhedral perihamiltonian graphs containing no adjacent cubic vertices.
论文关键词：Non-hamiltonian,Perihamiltonian,Hypohamiltonian
论文评审过程：Received 6 December 2019, Revised 24 September 2020, Accepted 27 September 2020, Available online 20 October 2020, Version of Record 20 October 2020.
论文官网地址：https://doi.org/10.1016/j.amc.2020.125714
