Back to Search
Start Over
Characterizing forbidden subgraphs that imply pancyclicity in 4-connected, claw-free graphs.
- Source :
-
Discrete Mathematics . Oct2021, Vol. 344 Issue 10, pN.PAG-N.PAG. 1p. - Publication Year :
- 2021
-
Abstract
- In 1984, Matthews and Sumner conjectured that every 4-connected, claw-free graph contains a Hamiltonian cycle. This still unresolved conjecture has been the motivation for research into the existence of other cycle structures. In this paper, we consider the stronger property of pancyclicity for 4-connected graphs. In particular, we show that every 4-connected, { K 1 , 3 , N (i , j , k) } -free graph, where i , j , k ≥ 1 and i + j + k = 6 , is pancyclic. This, together with results by Ferrara, Morris, Wenger, and Ferrara et al. completes a characterization of the graphs Y such that every { K 1 , 3 , Y } -free graph is pancyclic. In addition, this represents the best known progress towards answering a question of Gould concerning a characterization of the pairs of forbidden subgraphs that imply pancyclicity in 4-connected graphs. [ABSTRACT FROM AUTHOR]
- Subjects :
- *HAMILTONIAN graph theory
*SUBGRAPHS
*COMPLETE graphs
*LOGICAL prediction
Subjects
Details
- Language :
- English
- ISSN :
- 0012365X
- Volume :
- 344
- Issue :
- 10
- Database :
- Academic Search Index
- Journal :
- Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 151607637
- Full Text :
- https://doi.org/10.1016/j.disc.2021.112522