Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Lower Bounds for the Average Genus of a CF-graph. | Lower Bounds for the Average Genus of a CF-graph Yichao Chen College of Mathematics and Econometrics Hunan University Changsha 410082 ycchen@ Submitted Nov 15 2009 Accepted Oct 28 2010 Published Nov 5 2010 Mathematics Subject Classifications 05C10 Abstract CF-graphs form a class of multigraphs that contains all simple graphs. We prove a lower bound for the average genus of a CF-graph which is a linear function of its Betti number. A lower bound for average genus in terms of the maximum genus and some structure theorems for graphs with a given average genus are also provided. 1 Introduction A graph is often denoted by G V E it is simple if it contains neither multiple edges nor self-loops. If a graph does not contain self-loops but contains multiple edges we call it a multigraph otherwise if it contains self-loops we call it a pseudograph. The graph with only one vertex and no edges is called the trivial graph. The vertex-connectivity k G of a graph G is the minimum number of vertices whose removal from G results in a disconnected or trivial graph. The edge-connectivity K1 G of G is the minimum number of edges whose removal from G results in a disconnected or trivial graph. A spanning tree of G is a tree which is a subgraph of G with the same vertex set as G. For a spanning tree of G the number of co-tree edges is called the Betti number of G denoted by h G . A surface means a compact closed 2-manifold without boundary. It is known that there are two kinds of surfaces orientable and nonorientable. An embedding of G into a surface S is a topological embedding i G S see 14 and each component of S i G called a region is homeomorphic to an open disk. In this paper we only consider embeddings of G into orientable surfaces S. A rotation at a vertex v of a graph G is a cyclic order of all edges incident with v thus an n-valent vertex admits n 1 rotations. A rotation system R of the graph is a collection of rotations one for each vertex of G. An .
