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-2chi)-trestles. They used the Discharging Method. For the remaining surfaces, upper bounds were obtained of 8-2chi for surfaces with chi between -9 and -5, and 10-2chi for chi between -1 and -4. The lower bound of 6-2chi 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