Journal or Publication Title:
Date of publication:
Volume:
ISSN:
Additional Information:
Քուլաքզյան Մ., Նիկողոսյան Ժ., Кулакзян М., Никогосян Ж.
Title:
On Longest Cycles in 2-connected Graphs
Other title:
2-կապակցված գրաֆների ամենաերկար ցիկլերի մասին; О длиннейших циклах 2-связных графов
Creator:
Mossine S. Koulakzian ; Zhora G. Nikoghosyan
Subject:
Uncontrolled Keywords:
Hamilton cycle ; Dominating cycle ; Longest cycle ; Longest path ; Minimum degree
Coverage:
Abstract:
For a graph G, n denotes the order (the number of vertices) of G, c the order of a longest cycle in G (called circumference), p the order of a longest path and ± the minimum degree. In 1952, Dirac proved: (i) if G is a 2-connected graph, then c ¸ minfn; 2±g. The bound 2± in (i) was enlarged independently by Bondy (1971), Bermond (1976) and Linial (1976) in terms of ¾2 - the minimum degree sum of two nonadjacent vertices: (ii) if G is a 2-connected graph, then c ¸ minfn; ¾2g. In this paper two further extensions of (i) and (ii) are presented by incorporating p and the length of a vine on a longest path of G as new parameters along with n, ± and ¾2.