Spanning Trees And Maximum Genus Of Graphs

The graph genus is a topological invariant of a graph. By Duke's interpolation theorem for graph genus, determination of maximum genus of a graph G is very important for genus distribution of G. In this paper, we study the relationship between fundamental cycles and maximum gunus of graphs, and applications in upper-embedability of graphs. We show the following results:(1) By tree-transformation of a graph G, we can change the parity of the componentsof G - E(T) of a spanning tree T of G. Thus, we give a new proof of Huang-Liu's result. In particular,let G be a graph, and T be an optimal tree of G, we denote by G' a graph obtained from G by adding to a pair of adjacent edges e' and e" (with respect to T). Thenξ(G')≤ξ(G). Thusγ_M(G')≥γ_M(G) + 1. Particularly, if G is upper-embeddable, then G' is also upper-embeddable.Based on the above conclusions, we give a property of the set of all fundamental cycles corresponding to the optimal tree, which can be decomposed into two parts: One is {C₁,C₂,C₃,C₄,…,C_2k-1,C_2k}, where k =γ_M(G) and C_2i-1∩C_2i≠(?), (1≤i≤k); and another is {C_2k+1, C_2k+2,…, C_2k+s}, where s equals toξ(G) (the Betti deficiency of G), and any two of these fundamental cycles are disjoint.(2) Based on tree-transformation method, we show that a locally connected graph G has a very important property for distribution of odd component of co-tree:For a locally connected graph G, ifξ(G) = 1, given vertex x∈V(G), there must be an optimal tree T, such that x is contained in the unique odd component of G -E(T). As application, we give a new proof of famous L. Nebesk(?)'s theorem for upper-embedability of locally connected graphs.In general, we get some new type of upper-embeddable graphs G. Which is composed by two disjoint locally connected graphs G₁ and G₂ together with at least 2 edges joining them. It is clear that such upper-embedability can't be tested by the classical L. Nebesk(?)'s method. Further more, many new upper-embeddable graphs such as the permutation graphs and generalized graphs which are composed by two cycles are also discovered.