Relative Lengths of Paths and Cycles in 2-Connected Graphs

Authors

  • Zhora G. Nkoghosyan Institute for Informatics and Automation Problems of NAS RA

DOI:

https://doi.org/10.51408/1963-0040

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.

References

J.A.Bondy and U.S.R. Murty, Graph Theory with Applications, Mac millan,London and Elsevier,New York, 1976

G.A.Dirac,Some theorems on abstract graphs ", Proc. London,Math.Soc., vol.2,pp. 69-81,1952

J.A.Bondy,Basic GraphTheory: Paths and Circuits, Handbook of combinatorics,vol.1,2,Elsevier,Amsterdam,1990

J.A.Bondyand S.C.Locke,Relative lengths of paths and cyclesin k-connected graphs",Annals of Discrete Mathematics,vol.8,pp.253-259,1980.

S.C.Locke,Relative lengths of paths and cyclesin k-connected graphs",J.of Comb.Theory,SeriesB32,pp.206-222,1982.

Downloads

Published

2021-12-10

How to Cite

Nkoghosyan, Z. G. . (2021). Relative Lengths of Paths and Cycles in 2-Connected Graphs. Mathematical Problems of Computer Science, 52, 14–20. https://doi.org/10.51408/1963-0040

Issue

Vol. 52 (2019): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.