On light graphs in 3-connected plane graphs without triangular or quadrangular faces

Planar graphs; geometric and topological aspects of graph theory (05C10) Structural characterization of families of graphs (05C75) Three-dimensional polytopes (52B10)

Review text

A graph \(H\) is called light in a class {\(\mathcal H\)} of graphs if (i) at least one member of \(\mathcal H\) has a subgraph isomorphic to \(H\) and (ii) there is a number \(\phi=\phi(H,{\mathcal H})\) such that if \(G\in {\mathcal H}\) has any subgraph isomorphic to \(H\), then it has one whose vertices all have degree \(\leq \phi\). (Thus, the statement that every three-connected planar graph has a vertex of degree \(\leq 5\) means that the graph consisting of a single vertex is light, with \(\phi=5\), in the class of three-connected planar graphs.) The authors prove several results concerning graphs which are light in the classes \({\mathcal P}(3,5)\) and \({\mathcal P}(3, =5)\) of three-connected planar graphs in which each vertex has degree \(\geq 3\) and each face has size \(\geq 5\), respectively \(=5\). For example: (i) For each \(k\geq 3\), the \(k\)-path \(P_k\) is light in \({\mathcal P}(3,5)\), with \(\phi\leq {5\over 3}k\). (ii) An \(r\)-cycle is light in \({\mathcal P}(3, =5)\) if and only if \(r\) is one of 5, 8, 11 or 14.

Recommendations

Cited in

(23)

This page was built for publication: On light graphs in 3-connected plane graphs without triangular or quadrangular faces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956103)