Abstract:

Let G be a graph on n vertices with minimum degree ±. The earliest nontrivial lower bound for the circumference c (the length of a longest cycle in G) was established in 1952 due to Dirac in terms of n and ±: (i) if G is a 2-connected graph, then c ¸ minfn; 2±g. The bound in Theorem (i) is sharp. In 1986, Bauer and Schmeichel gave a version of this classical result for 1-tough graphs: (ii) if G is a 1-tough graph, then c ¸ minfn; 2±+2g. In this paper we present an improvement of (ii), which is sharp for each n: (iii) if G is a 1-tough graph, then c ¸ minfn; 2± + 2g when n ´ 1(mod 3); c ¸ minfn; 2± + 3g when n ´ 2(mod 3) or n ´ 1(mod 4); and c ¸ minfn; 2± + 4g otherwise
; Пусть С является п вершинным графом с минимальной степенью ±. В 1952г. Дирак получил первую нетривиальную оценку для длины с длиннейшего цикла графа С: (1) В любом 2-связном графе, с > тт{п, 2±}. Эту оценку в 1986г. Бауер и Шмейхель улучшили для 1-жестких графов: (н) В любом 1-жестком графе, с > тт{п, 2± + 2}. Полученные оценки достигаемы для определенных значений параметра п. В настоящей работе предлагается улучшение оценки Бауера и Шмейхелья, которое неулучшаема для всех значений параметра п.

Identifier:

oai:noad.sci.am:135906

DOI:

10.51408/1963-0017

ISSN:

0131-4645

Language:

English ; Английский

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

50

URL:

click here to follow the link

Additional Information:

zhora@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2018

Indexing:

ASCI