Skip to main content
Pancyclicity of 4-Connected {Claw, Generalized Bull}-Free Graphs
Discrete Mathematics
  • Michael Ferrara, University of Colorado at Denver
  • Silke Gehrke, Emory University
  • Ronald Gould, Emory University
  • Colton Magnant, Georgia Southern University
  • Jeffrey Powell, Samford University
Document Type
Publication Date

A graph G is pancyclic if it contains cycles of each length ℓ, 3≤ℓ≤|V(G)|. The generalized bull B(i,j) is obtained by associating one endpoint of each of the paths Pi+1 and Pj+1 with distinct vertices of a triangle. Gould, Łuczak and Pfender (2004) [4] showed that if G is a 3-connected {K1,3,B(i,j)}-free graph withi+j=4 then G is pancyclic. In this paper, we prove that every 4-connected, claw-free, B(i,j)-free graph with i+j=6 is pancyclic. As the line graph of the Petersen graph is B(i,j)-free for any i+j=7 and is not pancyclic, this result is best possible.

Citation Information
Michael Ferrara, Silke Gehrke, Ronald Gould, Colton Magnant, et al.. "Pancyclicity of 4-Connected {Claw, Generalized Bull}-Free Graphs" Discrete Mathematics Vol. 303 Iss. 4 (2013) p. 460 - 467 ISSN: 0012-365X
Available at: