tailieunhanh - Lower bounds for the maximum genus of 4-regular graphs

This paper investigates the maximum genus and upper embeddability of connected 4-regular graphs. We obtain lower bounds on the maximum genus of connected 4-regular simple graphs and connected 4-regular graphs without loops in terms of the Betti number. | Turk J Math 36 (2012) , 530 – 537. ¨ ITAK ˙ c TUB doi: Lower bounds for the maximum genus of 4-regular graphs ∗ Ding Zhou, Rongxia Hao, Weili He Abstract This paper investigates the maximum genus and upper embeddability of connected 4-regular graphs. We obtain lower bounds on the maximum genus of connected 4-regular simple graphs and connected 4-regular graphs without loops in terms of the Betti number. The definition of the Betti number is referred to [Gross and Tucker, Topological Graph Theory, New York, 1987]. Furthermore, we give examples that show that these lower bounds are tight. Key Words: Maximum genus, upper embeddable, Betti number 1. Introduction The maximum genus of a connected graph G = (V, E), denoted by γM (G), is the maximum integer k with the property that there exists a cellular embedding of G on the orientable surface with genus k . The maximum genus has received considerable attention after Nordhaus et al. [18]. Xuong [22] proved that every 4-edge connected graph is upper embeddable. However, there are many examples of 3-edge connected graphs and 2-edge connected graphs that are not upper embeddable. See, for example, [2, 12, 14]. Therefore, considerable attention is given to the lower bounds on the maximum genus of many kinds of graphs in terms of some graph invariants. See, for example, [3, 5, 7, 10]. Chen et al. [2] proved that for a 2-connected simple graph with all its vertices of degree greater than 2, the maximum genus is at least β(G)/3 . Chen and Huang gave some results on the maximum genus of graphs in [4]. In the paper [15], Nedela and Skoviera proved that any Eulerian graph with at most 2 vertices of degree 0 (mod 4) is necessarily upper embeddable. In particular, any connected regular graph with degree 4k + 2 , for an integer k ≥ 1 , is upper embeddable. Skovieria [20, 21] has obtained the maximum genus of graphs which are 3-regular with 2-factor triangles, and its slightly weaker form of the result was .