Premium
Pancyclicity of 4‐Connected, Claw‐Free, P 10 ‐Free Graphs
Author(s) -
Ferrara Michael,
Morris Timothy,
Wenger Paul
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21626
Subject(s) - combinatorics , mathematics , pancyclic graph , claw , graph , line graph , discrete mathematics , pathwidth , biology , ecology
Abstract A graph G is said to be pancyclic if G contains cycles of all lengths from 3 to | V ( G ) | . We show that if G is 4‐connected, claw‐free, and P 10 ‐free, then G is either pancyclic or it is the line graph of the Petersen graph. This implies that every 4‐connected, claw‐free, P 9 ‐free graph is pancyclic, which is best possible and extends a result of Gould et al. Pancyclicity in 3‐connected graphs: Pairs of forbidden subgraphs, [J Graph Theory 47 (2004), 183–202].