New sufficient conditions for hamiltonian and pancyclic graphs

Ingo Schiermeyer; Mariusz Woźniak

Discussiones Mathematicae Graph Theory (2007)

  • Volume: 27, Issue: 1, page 29-38
  • ISSN: 2083-5892

Abstract

top
For a graph G of order n we consider the unique partition of its vertex set V(G) = A ∪ B with A = {v ∈ V(G): d(v) ≥ n/2} and B = {v ∈ V(G):d(v) < n/2}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.

How to cite

top

Ingo Schiermeyer, and Mariusz Woźniak. "New sufficient conditions for hamiltonian and pancyclic graphs." Discussiones Mathematicae Graph Theory 27.1 (2007): 29-38. <http://eudml.org/doc/270642>.

@article{IngoSchiermeyer2007,
abstract = {For a graph G of order n we consider the unique partition of its vertex set V(G) = A ∪ B with A = \{v ∈ V(G): d(v) ≥ n/2\} and B = \{v ∈ V(G):d(v) < n/2\}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.},
author = {Ingo Schiermeyer, Mariusz Woźniak},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hamiltonian graphs; pancyclic graphs; closure},
language = {eng},
number = {1},
pages = {29-38},
title = {New sufficient conditions for hamiltonian and pancyclic graphs},
url = {http://eudml.org/doc/270642},
volume = {27},
year = {2007},
}

TY - JOUR
AU - Ingo Schiermeyer
AU - Mariusz Woźniak
TI - New sufficient conditions for hamiltonian and pancyclic graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 1
SP - 29
EP - 38
AB - For a graph G of order n we consider the unique partition of its vertex set V(G) = A ∪ B with A = {v ∈ V(G): d(v) ≥ n/2} and B = {v ∈ V(G):d(v) < n/2}. Imposing conditions on the vertices of the set B we obtain new sufficient conditions for hamiltonian and pancyclic graphs.
LA - eng
KW - hamiltonian graphs; pancyclic graphs; closure
UR - http://eudml.org/doc/270642
ER -

References

top
  1. [1] A. Ainouche and N. Christofides, Semi-independence number of a graph and the existence of hamiltonian circuits, Discrete Appl. Math. 17 (1987) 213-221, doi: 10.1016/0166-218X(87)90025-4. 
  2. [2] J.A. Bondy, Pancyclic graphs I, J. Combin. Theory 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5. Zbl0183.52301
  3. [3] J.A. Bondy and V. Chvátal, A method in graph theory, Discrete Math. 15 (1976) 111-136, doi: 10.1016/0012-365X(76)90078-9. Zbl0331.05138
  4. [4] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Elsevier North Holland, New York, 1976). Zbl1226.05083
  5. [5] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. Zbl0047.17001
  6. [6] R.J. Faudree, R.Häggkvist and R.H. Schelp, Pancyclic graphs - connected Ramsey number, Ars Combin. 11 (1981) 37-49. Zbl0485.05038
  7. [7] E. Flandrin, H. Li, A. Marczyk and M. Woźniak, A note on a new condition implying pancyclism, Discuss. Math. Graph Theory 21 (2001) 137-143, doi: 10.7151/dmgt.1138. Zbl0989.05064
  8. [8] G. Jin, Z. Liu and C. Wang, Two sufficient conditions for pancyclic graphs, Ars Combinatoria 35 (1993) 281-290. Zbl0788.05059
  9. [9] O. Ore, Note on hamilton circuits, Amer. Math. Monthly 67 (1960) 55, doi: 10.2307/2308928. 
  10. [10] E.F. Schmeichel and S.L. Hakimi, A cycle structure theorem for hamiltonian graphs, J. Combin. Theory (B) 45 (1988) 99-107, doi: 10.1016/0095-8956(88)90058-5. Zbl0607.05050

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.