scientific article; zbMATH DE number 4120198
[For the entire collection see Zbl 0656.00008.] Let G be a cubic 3-connected planar graph, and let C be a cycle in G. A bridge over C is the graph induced by the vertices in a component of \(G\setminus C\), together with those vertices of C adjacent to vertics in this component. The authors prove that given integers q and w, it is possible to find a cubic 3-connected planar graph G such that (a) any face of G has length at most q, (b) for any longest cycle C there is a bridge B over C such that B meets C in at least w vertices, (c) the ratio of the length of a longest cycle to the total number of vertices is as small as desired. This result is proved by construction, and extends previous work of \textit{H. Walther} and \textit{H.-J. Voß} [in ``Über Kreise in Graphen (1974; Zbl 0288.05101); pp. 58-62], where it was proved without the restriction on the length of a face.
- Graham's problem on shortest networks for points on a circle
- Bridges of longest cycles
- Pentagonal 3-polytopal graphs with edges of only two types and shortness parameters
- Computing and counting longest paths on circular-arc graphs in polynomial time
- An extension to ‘an algorithm for rinding a circuit of even length in a directed graph’
- Canonical forms for cycles in bridge graphs
- Longest cycles in cyclically 4-edge-connected cubic planar graphs
- Regular graphs in which every pair of points is missed by some longest cycle
- Shortness parameters of polyhedral graphs with few distinct vertex degrees
- Longest-edge \(n\)-section algorithms: properties and open problems
- Chords of longest circuits in locally planar graphs
- A note on 3-connected cubic planar 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 Q4733880)