Abstract
Schmeichel and Hakimi [5], and Bauer and Schmeichel [1] gave an evidence in support of the well-known Bondy’s “metaconjecture” that almost any non-trivial condition on graphs which implies that the graph is hamiltonian also implies that it is pancyclic. In particular, they proved that the metaconjecture is valid for Chvátal’s condition [3]. We slightly generalize their results giving a new Chvâtal type condition for pancyclicity.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bauer, D., Schmeichel, E.: Hamiltonian degree conditions which imply a graph is pancyclic. J. Comb. Theory B 48, 111–116 (1990)
Bondy, J.A., Chvâtal, V.: A method in graph theory. Discrete Math. 15, 111–136 (1976)
Chvâtal, V.: On hamilton’s ideals. J. Comb. Theory B 12, 163–168 (1972)
Gould, R.J.: Updating the hamiltonian problem — a survey, J. Graph Theory 15, 121–157 (1991)
Schmeichel, E., Hakimi, S.L.: Pancyclic graphs and a conjecture of Bondy and Chvâtal, J. Comb. Theory B 17, 22–34 (1974)
Zhang, S.: Pancyclism and bipancyclism of hamiltonian graphs, J. Comb. Theory B 60, 159–168 (1994)
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of author was partially supported by Grant No. 2/1138/94 “Computational models, algorithms and complexity” of Slovak Academy of Sciences and by EC Cooperative Action IC1000 “Algorithms for Future Technologies” (Project ALTEC)
Rights and permissions
About this article
Cite this article
Stacho, L. A New Chvátal Type Condition for Pancyclicity. Graphs and Combinatorics 13, 275–280 (1997). https://doi.org/10.1007/BF03353005
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF03353005