Spanning planar subgraphs of graphs in the torus and Klein bottle (Q1898728): Difference between revisions

Since Whitney's 1931 major results on the Hamiltonian properties of planar graphs, many generalizations to graphs on surfaces have been found. Two concepts of interest in this respect are that of a \(k\)-walk and an \(m\)-tree. A \(k\)-walk in a graph is a closed walk that visits every vertex at least once and at most \(k\) times. An \(m\)-tree is a spanning tree with maximum degree at most \(m\). The paper under review contains a useful summary of known results about these properties for graphs embedded in surfaces. The torus and Klein bottle are the only surfaces for which the existence of 2-walks for 3-connected graphs is an open question. The main result of the paper settles this question by showing that every 3-connected graph embeddable in the torus or Klein bottle has a 2-walk and a 3-tree.