Long cycles passing through a specified edge in a 3-connected graph. (English) Zbl 0868.05033

Enomoto, Hikeo; Hirohata, Kazuhide; Ota, Katsuhiro

J. Graph Theory 24, No. 3, 275-279 (1997).

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.

Reviewer: N.F.Quimpo (Manila)

MSC:

05C38

Paths and cycles

Keywords:

long cycle