New Extensions of Dirac's Theorems

Authors

  • Mossine S. Koulakzian Institute for Informatics and Automation Problems of NAS RA
  • Carlen M. Mosesyan Kh. Abovyan Armenian State University
  • Zhora G. Nikoghosyan Institute for Informatics and Automation Problems of NAS RA

Keywords:

Hamilton cycle, Longest cycle, Circumference, Minimum degree, Degree sequence

Abstract

Let G be a graph on n vertices with degree sequence δ = d1≤d2 • ≤ dn and let c be the circumference - the length of a longest cycle in G. In 1952, Dirac proved: (i) every graph with d1 ≥n/2 n 2 is hamiltonian; (ii) in every 2-connected graph, c≥ min{n,2d1}. In this paper we present the following two Dirac-type extensions: (iii) every graph with d δ ≥n/2is hamiltonian; (iv) in every 2-connected graph, c≥ min{n,2dδ}. The results are sharp. Keywords: Hamilton cycle, Longest cycle, Circumference, Minimum degree, Degree sequence.

References

J. A . Bondy, " Basic graph theory - paths and cycles" , Handbook of Combinatorics, vol.1 , Elsevier, A msterdam, pp. 5-110, 1995.

J. A . Bondy and U S.R. Murty, Graph Theory with Applications, Macmillan, London and Elsevier, New York 1976.

G. A . Dirac, ’’ Some theorems on abstract graphs" , Proc. London, Math. Soc., vol. 2, pp. 69-81 , 1952.

Downloads

Published

2021-12-10

How to Cite

Koulakzian, M. S., Mosesyan, C. M., & Nikoghosyan, Z. G. (2021). New Extensions of Dirac’s Theorems. Mathematical Problems of Computer Science, 48, 14–18. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/115

Issue

Vol. 48 (2017): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.