НАН РА. Математические вопросы кибернетики и вычислительной техники=Mathematical problems of computer science

On Long Cycles in Graphs in Terms of Degree Sequences

Koulakzian, Mossine S. (2017) On Long Cycles in Graphs in Terms of Degree Sequences. Математические вопросы кибернетики и вычислительной техники, № 48. pp. 19-22. ISSN 0131-4645

[img]
Preview
PDF
Download (265Kb) | Preview

    Abstract

    Let G be a graph on n vertices with degree sequence δ = d1 ≤ d2 ≤ ... ≤ dn. Let m be the number of connected components of G, c the circumference - the order of a longest cycle, p the order of a longest path in G and ¾s the minimum degree sum of an independent set of s vertices. In this paper it is shown that in every graph G, c ≥ dm+m + 1. This bound is best possible and generalizes the earliest lower bound for the circumference due to Dirac (1952): c ≥ δ +1 = d1 +1. As corollaries, we have: (i) c ≥ d+1 + 1; (ii) if dσm+m ≥p-1, then c = p; (iii) if G is a connected graph with d±+1≥p-1, then G is hamiltonian; (iv) if dσm+m ≥ n - 1, then G is hamiltonian.

    Item Type: Article
    Additional Information: Գրաֆներում երկար ցիկլերի մասին աստիճային հաջորդականությունների լեզվով / Մ. Քուլաքզյան: О длиннейших циклах графа в терминах последовательности степеней вершин / М. Кулакзян
    Uncontrolled Keywords: Hamilton cycle, Longest cycle, Circumference, Minimum degree, Degree sequence.
    Subjects: Q Science > QA Mathematics > Graph theory
    Divisions: UNSPECIFIED
    Depositing User: FSL Bibl. Dept.
    Date Deposited: 10 Oct 2018 14:49
    Last Modified: 15 Oct 2018 14:50
    URI: http://compsci.asj-oa.am/id/eprint/879

    Actions (login required)

    View Item