Two Generalized Lower Bounds for the Circumference

Authors

  • Mossine S. Koulakzian Institute for Informatics and Automation Problems of NAS RA
  • Zhora G. Nikoghosyan Institute for Informatics and Automation Problems of NAS RA

DOI:

https://doi.org/10.51408/1963-0002

Keywords:

Degree sums, Circumference, Minimum degree

Abstract

In 2013, the second author obtained two lower bounds for the length of a longest cycle C in a graph G in terms of the length of a longest path (a longest cycle) in G¡C and the minimum degree of G (Zh.G. Nikoghosyan, "Advanced Lower Bounds for the Circumference", Graphs and Combinatorics 29, pp. 1531-1541, 2013). In this paper we present two analogous bounds based on the average of the ¯rst i smallest degrees in G ¡ C for appropriate i instead of the minimum degree

References

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

Zh.G. Nikoghosyan, '' Advanced lower bounds for the circumference", Graphs and Combinatorics 29, pp. 1531-1541,2013.

Downloads

Published

2021-12-10

How to Cite

Koulakzian, M. S., & Nikoghosyan, Z. G. (2021). Two Generalized Lower Bounds for the Circumference. Mathematical Problems of Computer Science, 49, 18–25. https://doi.org/10.51408/1963-0002

Issue

Vol. 49 (2018): 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.