Genus Polynomials For Some Kinds Of Digraphs And Graphs

In this paper,the genus distributions of two kinds of digraphs and graphs in orientable surfaces are studied.In topolodical graph theory,the surface S is a compact 2-dimensional manifold without boundary.The classical topology theory shows that the orientable sur-face of genus h,denoted by Sh,is the sphere with h handles added.The study of the number of 2-cell embedding of a given graph in Sh is an important subject in topology theory.There are many results about the genera of graphs,but little is known about em-bedding genera for digraphs.A graph G is said to be embedded in a surface S if there exist a one-one mapping ?:G ? S,such that each connected component of S-?(G)homeomorphic with an open disk.? is called a cell embedding of G.We study the genus polynomials of given digraphs and graphs using the joint trees method and transfer matrix given by Yanpei Liu and Bojan Mohar respectively.The organization structures are as follows:In chapter 1,we introduce the concepts and background of graph embedding on ori-entable surfaces.In chapter 2,we study the embedding genus distribution of quasi square diagraph in orientable surface by using the joint trees method,and obtain the genus polynomials.In chapter 3,we depicts the embedding genus distributions of quasi claw diagraphs in orientable surfaces and obtain the genus polynomials.In chapter 4,we use the transfer matrix proposed by Bojan Mohar to study the genus distribution of double chain graphs.In chapter 5,we give the conclusions and the further research directions.