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

Harant, Jochen; Walther, Hansjoachim

Čas. Pěstování Mat. 112, 114-122 (1987).

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

Keywords:

3-polytopes; Hamiltonian circuit; shortness exponent; maximal length of a circuit; regular graphs

Citations:

Zbl 0492.05051