Study Of Genus Distributions For Some Graphs

The genus distribution was firstly introduced by Gross and Furst in [19], as one of important topological invariants of graphs. It entirely describe that the distribution of the number of the all embeddings. which on the given and orientable surfaces that the graph can be embeded into. Its theory has been applied in judgmenting graph isomorphism, calculating of complex algebraic curve mode space, quantum field theory and string theory of theoretical physics and so on. Since the last century, many famous scholars at home and abroad in the research of this field. For example:White, Gross, Mohar, Stahl, Tuck-er, Bonnington, Furst, Tesar and domestic Professor Liu Yanpei, and so on. However, Thomassen has been proven that calculating the genus distributions of the general graphs is NP-complete. Because of its difficulty, the results of the genus distributions of the graphs aren’t very rich, and the classes of graphs whose the genus distribution can be determined have special structures, which makes that many of methods can’t be generalized to general graphs. In this paper, we try to apply some new methods to explore the genus distributions of some graph classes, several results are derived as follows:1. Let (G,u,v) be a double-rooted graph with two 2-valent co-roots u and v. In 2011, Gross studied the genus distribution of the graph comformed by self-pasting at root vertices of the graph (G, u, v) in literature [15]. In the second chapter of this paper, the genus distribution of a double-rooted graph whose one root has arbitrary degree after self-pasting at root vertices have been derived, by applying vertex-deleting, edge-addition theorem, multiple production rules and self-amalgamation theorem; And analogous results of "t-wo roots are two-degree" in literature [15] had been provided by Gross have been generalized.2. D3×Pn is the cartesian product of a dipole graph D3 and a path Pn. We derive a recursion for the genus distribution of the graph D3×Pn, with the aid of skillfully introducing a new kind of edges-adding operations and combining the partial genus distribution of the graph.3. Calculating the genus distributions of outerplanar graphs is a con-cerned topic in topological graph theory. In the forth chapter of this paper, we concider the genus distribution for a type of 5-regular outerplanar graph On. Using rooted-graphs, we derive simultaneous recursions for the partial genus distribution of the graph (Rn,p,q) constructed by an open chain of n copies of a base graph (R1,p,q), and a recursion formula for the genus distribution of the graphs On formed by modified edge-addition on (Rn,p, q).4. In the fifth chapter of this paper,through smart applications of transfer matrix method and vectorized production matrix in combination, the calcu-lation formulas for the genus distributions of two types of graphs formed by double-path connect in series are derived.