Minimum Degree and Size Conditions for Hamiltonian and Traceable Graphs

Abstract

A graph is called Hamiltonian (resp. traceable) if the graph has a Hamiltonian cycle (resp. path), a cycle (resp. path) containing all the vertices of the graph. In this note, we present sufficient conditions involving minimum degree and size for Hamiltonian and traceable graphs. One of the sufficient conditions strengthens the result obtained by Nikoghosyan in [1].

Keywords

• Hamiltonian graph,Minimum degree,Traceable graph

References

1. [1] Zh. G. Nikoghosyan, A size bound for Hamilton cycles, (2011), arXiv:1107.2201 [math.CO].
2. [2] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York, 1976.
3. [3] Zh. G. Nikoghosyan, Two sufficient conditions for Hamilton and dominating cycles, Int. J. Math. Math. Sci., 2012 (2012), Article ID 185346, 25 pages, doi:10.1155/2012/185346.
4. [4] K. Zhao, Dirac type condition and Hamiltonian graphs, Serdica Math. J. 37 (2011), 277–282.
5. [5] D. W. Cranston, S. O, Hamiltonicity in connected regular graphs, Inform. Process. Lett., 113 (2013), 858–860.