On light graphs in 3-connected plane graphs without triangular or quadrangular faces. (English) Zbl 0988.05031

Jendrol, Stanislav; Owens, Peter J.

Graphs Comb. 17, No. 4, 659-680 (2001).

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.

Reviewer: Carl Droms (Harrisonburg)

MSC:

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

Keywords:

light graph; 3-connected planar graph