Title:

Relative Lengths of Paths and Cycles in 2-Connected Graphs

Author:

Nkoghosyan Zhora G.

Type:

Article

Uncontrolled Keywords:

Longest cycle ; Longest path ; Circumference ; Vine

Abstract:

Let l be the length of a longest path in a 2-connected graph G and c the circumference - the length of a longest cycle in G. In 1952, Dirac proved that c , by noting that "actually c , but the proof of this result, which is best possible, is rather complicated". Let L1;L2; :::;Lm be a vine on a longest path of G. In this paper, using the parameter m, we present a more general sharp bound for the circumference c including the bound c as an immediate corollary, based on elementary arguments.

Publisher:

"GITUTYUN" PUBLISHING HOUSE OF NAS RA

Date of publication:

2019-12-25

DOI:

10.51408/1963-0040

ISSN:

2579-2784

Language:

English

Journal or Publication Title:

Mathematical Problems of Computer Science

Volume:

52

URL:


Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Country:

Armenia

Year:

2019