Premium
Weakly pancyclic graphs
Author(s) -
Brandt Stephan,
Faudree Ralph,
Goddard Wayne
Publication year - 1998
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/(sici)1097-0118(199803)27:3<141::aid-jgt3>3.0.co;2-o
Subject(s) - pancyclic graph , mathematics , combinatorics , graph , discrete mathematics , hamiltonian path , degree (music) , 1 planar graph , line graph , physics , acoustics
In generalizing the concept of a pancyclic graph, we say that a graph is “weakly pancyclic” if it contains cycles of every length between the length of a shortest and a longest cycle. In this paper it is shown that in many cases the requirements on a graph which ensure that it is weakly pancyclic are considerably weaker than those required to ensure that it is pancyclic. This sheds some light on the content of a famous metaconjecture of Bondy. From the main result of this paper it follows that 2‐connected nonbipartite graphs of sufficiently large order n with minimum degree exceeding 2 n /7 are weakly pancyclic; and that graphs with minimum degree at least n /4 + 250 are pancyclic, if they contain both a triangle and a hamiltonian cycle. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 141–176, 1998