Journal or Publication Title:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Date of publication:

2017

Volume:

48

ISSN:

0131-4645

Additional Information:

Քուլաքզյան Մ., Кулакзян М.

Other title:

Գրաֆներում երկար ցիկլերի մասին աստիճային հաջորդականությունների լեզվով; О длиннейших циклах графа в терминах последовательности степеней вершин

Coverage:

19-22

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.

Publisher:

Изд-во НАН РА

Date created:

2017-12-14

Format:

pdf

Identifier:

oai:arar.sci.am:258919

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան