Ամսագրի կամ հրապարակման վերնագիր:

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

Հրապարակման ամսաթիվ:

2017

Հատոր:

48

ISSN:

0131-4645

Լրացուցիչ տեղեկություն:

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

Այլ վերնագիր:

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

Ծածկույթ:

19-22

Ամփոփում:

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.

Հրատարակիչ:

Изд-во НАН РА

Ստեղծման ամսաթիվը:

2017-12-14

Ձևաչափ:

pdf

Նույնացուցիչ:

oai:arar.sci.am:258919

Բնօրինակի գտնվելու վայրը:

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