Publications

Pancyclicity of 4-connected $\{K_{1,3},Z_8\}$-free graphs.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Graphs and Combinatorics
Year: 2019
Abstract: A graph $G$ is said to be {\it pancyclic} if $G$ contains cycles of lengths from 3 to $|V(G)|$. For a positive integer $i$, we use $Z_i$ to denote the graph obtained by identifying an endpoint of the path $P_{i+1}$ with a vertex of a triangle. In 1984, Matthews and Sumner conjectured that every 4-connected claw-free graph is hamiltonian. Motivated by the Matthews-Sumner Conjecture, Ron Gould came up with the problem ``Characterize the pairs of forbidden subgraphs that imply a 4-connected graph is pancyclic'' at the 2010 SIAM Discrete Math Meeting in Austin, TX. In this paper, the authors show that every 4-connected claw-free $Z_8$-free graph either is pancyclic or is the line graph of the Petersen graph, a result which implies that every 4-connected claw-free $Z_6$-free graph is pancyclic, and every 5-connected claw-free $Z_8$-free graph is pancyclic.
Link: Pancyclicity of 4-connected $\{K_{1,3},Z_8\}$-free graphs.