Open AccessTwo Generalized Lower Bounds for the Circumference
Author(s) -
Mossine S. Koulakzian,
Zh. G. Nikoghosyan
Publication year - 2018
Publication title -
mathematical problems of computer science
Language(s) - English
Resource type - Journals
eISSN - 2738-2788
pISSN - 2579-2784
DOI - 10.51408/1963-0002
Subject(s) - circumference , combinatorics , mathematics , degree (music) , graph , upper and lower bounds , path (computing) , geometry , physics , computer science , mathematical analysis , acoustics , programming language
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