Spanning Trees with Small Degrees

Whitney [W] showed that every 4-connected plane triangulation has a Hamiltonian path. This result is not true in general, as there are 4-connected triangulations of other surfaces that are not Hamiltonian. For example, take a 4-connected quadrangulation with more faces than vertices. Add a new vertex in each face and connect it to the four vertices on that face's boundary. The result is a 4-connected triangulation where the new vertices form an independent set. Since there are more new vertices than old, the graph is non-Hamiltonian.

A Hamiltonian path is a spanning tree of maximum degree 2. A relaxation is to search for spanning trees of small maximum degree. This search is helped if the embedded graph is locally planar. We measure this local planarity by the face-width, the minimum value of C intersect G taken over all noncontractible cycles C in the surface. Ellingham and Gao [EG] proved that every 4-connected graph embedded with sufficiently large face-width has a spanning tree of maximum degree at most 3. (The ``sufficiently large face-width'' depends on the genus of the surface.) The following conjectures that the number of degree-three vertices is not too large.

Conjecture: Let G be a 4-connected graph embedded in a surface of genus g with sufficiently large face-width. Then G contains a spanning tree with maximum degree 3 such that the number of vertices of degree 3 is O(g).

Mark Ellingham has written a survey article on results relating face-width, connectivity, and spanning trees [E]. I recommend it for additional background.

References:

[E] M. Ellingham, Spanning paths, cycles, trees, and walks for graphs on surfaces, Congressus Numerantium 115 (1996) 55-90.

[EG] M. Ellingham and Z. Gao, Spanning trees in locally planar triangulations, submitted.

[W] H. Whitney, A theorem on graphs, Ann. of Math. 32 (1931) 378-390.

Submitted by: Bojan Mohar, Department of Mathematics, University of Ljubljana, Jadranska 19, 61111 Ljubljana, Slovenia.

Send comments to dan.archdeacon@uvm.edu and to bojan.mohar@uni-lj.si

August, 1995