Long cycles in 3-connected graphs
From MaRDI portal
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})\).
Recommendations
- Long cycles in 3-cyclable graphs
- Longest cycles in 3-connected graphs
- scientific article; zbMATH DE number 568790
- scientific article; zbMATH DE number 4212091
- Long cycles passing through a specified edge in 3-connected graphs
- scientific article; zbMATH DE number 4008430
- Longest cycles in 3-connected planar graphs
- scientific article; zbMATH DE number 3906529
- scientific article; zbMATH DE number 986973
Cites work
- A Theorem on Planar Graphs
- Computing the orientable genus of projective graphs
- Convex programming and circumference of 3-connected graphs of low genus
- scientific article; zbMATH DE number 4008430 (Why is no real title available?)
- Longest cycles in 3-connected planar graphs
- Shortness exponents of families of graphs
- Simple paths on polyhedra
- Spanning planar subgraphs of graphs in the torus and Klein bottle
- The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices
- Trees in Polyhedral Graphs
Cited in
(44)- Convex programming and circumference of 3-connected graphs of low genus
- On cycles in 3-connected graphs
- Long paths and toughness of \(k\)-trees and chordal planar graphs
- The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
- An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs
- Long cycles in triangle-free graphs with prescribed independence number and connectivity
- Long cycles in graphs on a fixed surface
- Long cycles and 3-connected spanning subgraphs of bounded degree in 3- connected \(K_{1,d}\)-free graphs
- The circumference of a graph with no \(K_{3,t}\)-minor. II
- Tutte paths and long cycles in circuit graphs
- Planar Turán numbers of cycles: a counterexample
- Turing kernelization for finding long paths in graph classes excluding a topological minor
- Longer cycles in essentially 4-connected planar graphs
- On planar greedy drawings of 3-connected planar graphs
- Shortness coefficient of cyclically 4-edge-connected cubic graphs
- Toughness in graphs -- a survey
- Long induced paths in minor-closed graph classes and beyond
- Large \(W_k\)- or \(K_{3,t}\)-minors in 3-connected graphs
- Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
- Drawing planar graphs with many collinear vertices
- scientific article; zbMATH DE number 3902690 (Why is no real title available?)
- Cyclability of 3-connected graphs
- Long induced paths in 3-connected planar graphs
- Longest cycles in cyclically 4-edge-connected cubic planar graphs
- Toughness and longest cycles in 2-connected planar graphs
- scientific article; zbMATH DE number 4120198 (Why is no real title available?)
- Long cycles in 3‐connected graphs in orientable surfaces
- Long Paths in Random Apollonian Networks
- On longest paths and diameter in random Apollonian networks
- Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
- On longest cycles in essentially 4-connected planar graphs
- Enumerative properties of rooted circuit maps
- 2-connected spanning subgraphs of circuit graphs
- Dense circuit graphs and the planar Turán number of a cycle
- A new construction for the planar Turán number of cycles
- Counting cycles in planar triangulations
- Plane triangulations without large 2-trees
- Shortness parameters of polyhedral graphs with few distinct vertex degrees
- Dynamics of cycles in polyhedra. I: The isolation lemma
- Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs
- The circumference of a graph with no \(K_{3,t}\)-minor
- Longest cycles in 3-connected planar graphs
- Finding large cycles in Hamiltonian graphs
- A note on 3-connected cubic planar graphs
This page was built for publication: Long cycles in 3-connected graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850624)
