scientific article; zbMATH DE number 4120198

From MaRDI portal
Publication:4733880





[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.











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)