Long cycles in 3-connected graphs
Let \(\text{circ}(G)\) denote the the length of the longest cycle in a graph \(G\). \textit{J. W. Moon} and \textit{L. Moser} [Pac. J. Math. 13, 629-631 (1963; Zbl 0115.41001)] exhibited a 3-connected planar graph \(G\) with \(n\) vertices for which \(\text{circ}(G)\leq 9n^{\log_32}\). The present authors show that if \(G\) is a 3-connected graph with \(n\) vertices that is embeddable in the sphere, the projective plane, the torus, or the Klein bottle, then \(\text{circ}(G)\geq \Omega(n^{\log_32})\).
scientific article; zbMATH DE number 1843844
scientific article