×

zbMATH — the first resource for mathematics

Long cycles passing through a specified edge in a 3-connected graph. (English) Zbl 0868.05033
In a 1984 paper, H. Enomoto showed that each edge of a 3-connected noncomplete graph \(G\) lies in a long cycle of length \(\geq \min\{|V(G)|,\overline \sigma - 1 \}\), where \(\overline \sigma \) is the minimum degree sum of two nonadjacent vertices in \(G\), see [J. Graph Theory 8, 287-301 (1984; Zbl 0544.05044)]. He and his co-authors improve this result by showing that \(\overline \sigma \) can be replaced by the minimum degree sum of distance 2 vertices. They conjecture that the latter can be further replaced by twice the minimum of \(\max\{d(u),d(v)\}\), taken over distance 2 vertices.

MSC:
05C38 Paths and cycles
Keywords:
long cycle
PDF BibTeX XML Cite
Full Text: DOI