scientific article; zbMATH DE number 1496607

DOI10.1002/1097-0118(200007)34:3%3C221::AID-JGT3%3E3.0.CO;2-TMaRDI QIDQ4500709zbMATH OpenFDO

Authors D. K. Menser, M. N. Ellingham

Publication date 28 November 2001

Full work available at URL https://doi.org/10.1002/1097-0118(200007)34:3%3C221::AID-JGT3%3E3.0.CO;2-T

zbMATH Keywords

circumferencegirthlongest circuitminimum degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

A new lower bound on circumference (the length of a longest circuit) \(c(G)\) of a graph \(G\) in terms of girth \(g\) and minimum degree \(\delta\) of \(G\) is obtained in this paper as follows: \[ c(G) \geq \delta (\delta -1) ^ {\lfloor (g-3)/4 \rfloor} (p + 4/(\delta -2)) - g - 8/(\delta -2) \] where \(p \in \{ 1,2,3,4\}\) and \(p \equiv g+2\) (mod(4)). This new bound improves a few earlier results by Voss, Peyrat and Zhang.

Recommendations

• Advanced lower bounds for the circumference
• Circumference and girth
• scientific article; zbMATH DE number 4189767
• Maximal cycles in graphs of large girth
• scientific article; zbMATH DE number 147640

Cites work

• A new series of dense graphs of high girth
• Circumference and girth
• scientific article; zbMATH DE number 49078 (Why is no real title available?)
• On a graph theorem by dirac
• On the edge-chromatic number of a graph

Cited in

(10)

• Spanning paths in graphs
• Length of longest cycles in a graph whose relative length is at least two
• Advanced lower bounds for the circumference
• Circumference and girth
• Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs
• Maximal cycles in graphs of large girth
• scientific article; zbMATH DE number 4189767 (Why is no real title available?)
• Radius, girth and minimum degree
• Implicit-degrees and circumferences
• Cycle lengths in sparse graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4500709)