Spanning closed walks with bounded maximum degrees of graphs on surfaces

2017/11/30 by Morteza Hasanvand, Hasanvand, Morteza
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.1712.00125

Abstract

Gao and Richter (1994) showed that every 3-connected graph which embeds on the plane or the projective plane has a spanning closed walk meeting each vertex at most 2 times. Brunet, Ellingham, Gao, Metzlar, and Richter (1995) extended this result to the torus and Klein bottle. Sanders and Zhao (2001) obtained a sharp result for higher surfaces by proving that every 3-connected graph embeddable on a surface with Euler characteristic χ≤ -46 admits a spanning closed walk meeting each vertex at most \lceil (6-2χ)/(3)\rceil times. In this paper, we develop these results to the remaining surfaces with Euler characteristic χ≤ 0.

Related

• Topologically Trivial Closed Walks in Directed Surface Graphs
• Spanning Euler tours and spanning Euler families in hypergraphs with\n particular vertex cuts
• Computing the second and third systoles of a combinatorial surface
• On the maximum order of graphs embedded in surfaces
• Shortest path embeddings of graphs on surfaces