Expectation Of Embedding Graphs In Surfaces

Topological graph theorists first computed minimum genera of some classes of graphs. In the 1970's, a considerable amount of attention was given to maximum genus of a graph. Later, a considerable amount of attention was given to average genus of a graph. However the study on the average genus of an individual graph is presently only in the preprint stage. This disseration proposes to look at the average genus (average crosscap number) of graphs. It consists of six chapters.In Chapter 1, we investigated the graphs which does not contain three forbidden configurations. It is shown that the lower bound of average genus of a graph G which doesn't contain three forbidden configurations is a linear function of Betti number.Theorem 1 Let G be a connected graph with minimum degree at least 3, and G does not contain the structure of Fig. 1. ThenTheorem 2 Let G be a 2-edge-connected graph without self-loops. If it's minimum degree at least 3 and does not contain the second structure of Fig. 1, thenAlso some new lower bounds of average genus are obtained and the results of [2,3,6] are generalized. The main theorems areTheorem 3 Let G be a 2-edge connected simplicial graph with minimum degree at least 3. ThenTheorem 4 The average genus for a graph of maximum degree at most d is not less than 1/(d-1) its maximum genus.Theorem 5 Let r be a finite number. Then only finite many graphs which does not contain the structure of Fig. 1 have average genus less than r.