# zbMATH — the first resource for mathematics

On light graphs in 3-connected plane graphs without triangular or quadrangular faces. (English) Zbl 0988.05031
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.

##### 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
Full Text: