Embedding Distribution Of A Graph And Its Limit

A graph in 3-dimensional space is represented by the points which are connected by lines.The points in 3-dimensional space are vertices of the graph,and the lines connecting them are edges of the graph.A graph G=(V(G)?E(G))is composed of a nonempty set of vertices V(G)and a set of edges E(G)without crossing vertices.The genus distribution of a graph G is the sequence:?k(G),k=0,1,…,where ?k(G)denotes the number of distinct embeddings of G on the orientable surface Ok.The Euler-genus distribution of graph G refers to the sequence?i(G),i=0,1,…,where ?i(G)denotes the number of distinct embeddings of the graph G on the surface with Euler genus i.When we say the embedding distribution of a graph G,we mean its genus distribution or Euler genus distribution.The embedding distributions of graphs are one of main research areas in topological graph theory.In this paper,we study the enumeration,expectation value and limit of embedding distributions of some sequences of graphs.Let us demonstrate our results in details.(1)Derive a recurrence relation for the Euler-genus distributions of a family of nonlinear sequence of graphs.In Chapter 2,we obtain the Euler-genus distributions of cubic caterpillar-Halin graphs using the overlap matrix method;we also calculate the numbers of embeddings of cubic caterpillar-Halin graphs on the surfaces with small Euler-genus.(2)Obtain explicit expressions of the Euler-genus distributions of a family of linear sequence of graphs.In Chapter 3,first,we demonstrate a general method to calculate the Euler-genus distributions of linear sequence of graphs;then,applying this method,we obtain explicit expressions of the Euler-genus distributions of ladder-like sequence of graphs.(3)Give explicit formulas for the average genus of two important families of graphs.In Chapter 4,with the help of combination method and ordinary differential equations,we demonstrate a new method to calculate the average genus of graphs.Also,we obtain the average genus of the bouquet Bn and the dipole Dn.The previous results,which was obtained Stahl in 1991,only give their asymptotic estimates.(4)Find and prove the limit for the embedding distributions of linear sequence of graphs.When the number of edges or vertices of a graph is large,the value of the embedding distribution will be very huge,and its calculation will be very difficult.If you want to know the global feature of the embedding distribution,you need to consider its limit.In Chapter 5,under certain conditions,it is proved that the limit of the embedding distribution of H-linear sequence of graphs with spiders {Gn}(n=1)? is a normal distribution.As corollaries,we also prove that the embedding distribution(genus distribution and Euler genus distribution)of pathlike sequence of graphs and ladder-like sequence of graphs are asymptotic to normal distributions.(5)Show that the limit of the embedding distributions of tree-like sequence of graphs is a normal distribution.When a sequence of graphs are obtained by bar-amalgamation,this sequence of graphs is called a tree-like sequence of graphs.In Chapter 6,based on the observation that bar-amalgamation essentially corresponding to the addition of two independent random variables,this paper finally proves that the limit of the embedding distributions of tree-like sequence of graphs is a normal distribution.These results establish a connection between topological graph theory and probability theory.