TY - JOUR
T1 - Toughness, Forbidden Subgraphs and Pancyclicity
AU - Zheng, Wei
AU - Broersma, Hajo
AU - Wang, Ligong
N1 - Funding Information:
Supported by the National Natural Science Foundation of China (no. 11871398), the Natural Science Basic Research Plan in Shaanxi Province of China (no. 2018JM1032) and the China Scholarship Council (no. 201706290168)
Publisher Copyright:
© 2021, The Author(s).
PY - 2021/5
Y1 - 2021/5
N2 - Motivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such that every 1-tough H-free graph is hamiltonian. The almost complete answer was given there by the conclusion that every proper induced subgraph H of K1∪ P4 can act as a forbidden subgraph to ensure that every 1-tough H-free graph is hamiltonian, and that there is no other forbidden subgraph with this property, except possibly for the graph K1∪ P4 itself. The hamiltonicity of 1-tough K1∪ P4-free graphs, as conjectured by Nikoghosyan, was left there as an open case. In this paper, we consider the stronger property of pancyclicity under the same condition. We find that the results are completely analogous to the hamiltonian case: every graph H such that any 1-tough H-free graph is hamiltonian also ensures that every 1-tough H-free graph is pancyclic, except for a few specific classes of graphs. Moreover, there is no other forbidden subgraph having this property. With respect to the open case for hamiltonicity of 1-tough K1∪ P4-free graphs we give infinite families of graphs that are not pancyclic.
AB - Motivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such that every 1-tough H-free graph is hamiltonian. The almost complete answer was given there by the conclusion that every proper induced subgraph H of K1∪ P4 can act as a forbidden subgraph to ensure that every 1-tough H-free graph is hamiltonian, and that there is no other forbidden subgraph with this property, except possibly for the graph K1∪ P4 itself. The hamiltonicity of 1-tough K1∪ P4-free graphs, as conjectured by Nikoghosyan, was left there as an open case. In this paper, we consider the stronger property of pancyclicity under the same condition. We find that the results are completely analogous to the hamiltonian case: every graph H such that any 1-tough H-free graph is hamiltonian also ensures that every 1-tough H-free graph is pancyclic, except for a few specific classes of graphs. Moreover, there is no other forbidden subgraph having this property. With respect to the open case for hamiltonicity of 1-tough K1∪ P4-free graphs we give infinite families of graphs that are not pancyclic.
KW - Forbidden subgraph
KW - Hamiltonian graph
KW - Pancyclic graph
KW - Toughness
KW - UT-Hybrid-D
UR - http://www.scopus.com/inward/record.url?scp=85101239123&partnerID=8YFLogxK
U2 - 10.1007/s00373-021-02284-y
DO - 10.1007/s00373-021-02284-y
M3 - Article
AN - SCOPUS:85101239123
SN - 0911-0119
VL - 37
SP - 839
EP - 866
JO - Graphs and combinatorics
JF - Graphs and combinatorics
ER -