2-Connected 7-coverings of 3-connected graphs on surfaces

摘要

An m-covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3-connected graph on a surface with Euler genus k greater than or equal to 2 with sufficiently large representativity has a 2-connected 7-covering with at most 6k-12 vertices of degree 7. We also construct, for every surface F-2 with Euler genus k greater than or equal to 2, a 3-connected graph G on F-2 with arbitrarily large representativity each of whose 2-connected 7-coverings contains at least 6k - 12 vertices of degree 7. (C) 2003 Wiley Periodicals, Inc. [References: 12]