## Some new results about the shortness exponent in polyhedral graphs.(English)Zbl 0642.05039

The shortness exponent of a family $$\Gamma$$ of graphs G is $$\sigma =\liminf_{G\in \Gamma}[\log h(G)]/[\log n(G)]$$ where n(G) denotes the number of vertices of G and h(G) the maximal length of a circuit on G. The authors consider 3-polyhedral 3-, 4-, and 5-regular graphs. Improving results of P. S. Owens [Discrete Math. 39, 199-209 (1982; Zbl 0492.05051)] they prove the existence of families of such graphs having just two types of faces, m-gons, $$m=3,4,5$$, and certain k-gons, whose shortness exponent is less than 1.
Reviewer: Ch.Schulz

### MSC:

 05C45 Eulerian and Hamiltonian graphs 52Bxx Polytopes and polyhedra

Zbl 0492.05051
Full Text: