Co-author(s) :

Nikoghosyan Zhora ; Никогосян Жора

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.
; Пусть п, с, р и ± обозначают число вершин графа С , длина длиннейшего цикла, число вершин длиннейшей цепи и минимальная степень графа. В 1952 году Дирак доказал, что (1) если С является 2-связным графом, то с > т т { п, 2±}: Эту оценку независимо расширили Бонди (1971), Бермонд и Линиал (1976) с помощью параметра а 2 (минимальная сумма степеней двух не соседних вершин): (н) если С является 2-связным графом, то с > т т { п , а 2}. В настоящей работе представлены две новые расширения оценок (1) и (11) помощью параметров р и длины плюща длиннейшей цепи графа С на ряду с параметрами п, ±, а 2.

Publisher:

Mathematical Problems of Computer Science

Identifier:

oai:noad.sci.am:135996

ISSN:

0131-4645

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

47

URL:

click here to follow the link

Additional Information:

mossine@hotmail.com ; zhora@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2017

Indexing:

ASCI