2-Connected Spanning Subgraphs of Bounded Degree

Given a 3-connected graph *G*, a *k-trestle* is a 2-connected spanning subgraph of *G* of maximum degree *k*. Thus a Hamilton cycle is a 2-trestle. Trestles were originally studied by Barnette who was interested in determining the structure of 3-connected planar graphs (they are not Hamiltonian in general). He proved that they had 15-trestles, and conjectured that they had 6-trestles, which he showed would be the best possible. Gao solved this problem [G], showing that not only do 3-connected plane graphs have 6-trestles, but 3-connected projective plane, torus, and Klein bottle graphs do as well. He used the technique of bridges.

For surfaces of Euler characteristic *chi* at most negative 10, Sanders and Zhao [SZ] showed the best possible result that 3-connected graphs embeddable on these surfaces have (6-2*chi*)-trestles. They used the Discharging Method. For the remaining surfaces, upper bounds were obtained of 8-2*chi* for surfaces with *chi* between -9 and -5, and 10-2*chi* for *chi* between -1 and -4. The lower bound of 6-2*chi *is expected to be best possible.

**Problem:** *Settle the problem for the remaining thirteen surfaces.*

Similar results can be obtained for higher connectivity. In particular, Nash-Williams conjectured that 4-connected toroidal graphs have 2 -trestles (i.e., are Hamiltonian). Sanders and Zhao [SZ] showed that every 4-connected graph of Euler characteristic at least zero has a 3-trestle. Duke showed that connectivity high enough guarantees a 2-trestle for every surface.

**Problem:** *Find interesting best possible results for different values of connectivity and* k.

**References:**

[G] Z. Gao, 2-connected coverings of bounded degree in 3-connected graphs, *J. Graph Theory* **20** (1995) 327-338.

[SZ] D. Sanders and Y. Zhao, On 2-connected spanning subgraphs with low maximum degree, *J. of Combin. Th. Ser. B* **74** (1998) 64**-**86.

Submitted by: Daniel Sanders, Department of Mathematics, The Ohio State University, Columbus, OH 43210 USA. [[Note added by Dan Archdeacon: Dan Sanders has since moved. I do not have his current address.]]

Send comments to *dan.archdeacon@uvm.edu *

August, 1995