Maximum Genus of the Generalized Permutation Graph

In this paper we prove that the generalized permutation graph G（n, k） is upper embeddable if it has at most two odd subcycles, and that the maximum genus of G（n, k） is more than 「β（G（n,k））/3」 in most cases.

A NOTE ON THE MAXIMUM GENUS OF 3-EDGE-CONNECTED NONSIMPLE GRAPHS

Let G be a 3 edge connected graph (possibly with multiple edges or loops), and let γ M(G) and β(G) be the maximum genus and the Betti number of G, respectively. Then γ M(G)≥β(G)/3 can be proved and this answers a question posed by Chen, et al. in 1996.F FIRST OR

A TIGHT LOWER BOUND ON THE MAXIMUM GENUS OF A 3-CONNECTED LOOPLESS MULTIGRAPH

It is proved that every 3 connected loopless multigraph has maximum genus at least one third of its cycle rank plus one if its cycle rank is not less than ten, and if its cycle rank is less than ten,it is upper embeddable.This lower bound is tight.There are infinitely many 3 connected loopless multigraphs attaining this bound.

LOWER BOUNDS ON THE MAXIMUM GENUS OF LOOPLESS MULTIGRAPHS

The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous known results. Thus, a picture of the lower bounds on the maximum genus of loopless multigraphs is presented.

Maximum Genus and Girth of a Graph

It is known (for example, see [4]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, we establish a best upper bound on the Betti deficiency of a graph bounded by its independence number and girth, and immediately obtain a new result on the maximum genus.

MAXIMUM GENUS,INDEPENDENCE NUMBER AND GIRTH

It is known (for example see [2]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, the authors establish an upper bound on the Betti deficiency in terms of the independence number as well as the girth of a graph, and thus use the formulation in [2] to translate this result to lower bound on the maximum genus. Meantime it is shown that both of the bounds are best possible.

Exponentially many maximum genus embeddings and genus embeddings for complete graphs

There are many results on the maximum genus, among which most are written for the existence of values of such embeddings, and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic graph G of order n always has at least $ (\sqrt 2 )^{m + n + \tfrac{\alpha } {2}} $ distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings) are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number n, there are at least $ C2^{\tfrac{n} {4}} $ many genus embeddings for complete graph K n with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and straight.

Nonseparating Independent Sets and Maximum Genus of Graphs

A subset I of vertices of an undirected connected graph G is a nonseparating independent set(NSIS)if no two vertices of I are adjacent and GI is connected.Let Z(G)denote the cardinality of a maximum NSIS of G.A nonseparating independent set containing Z(G)vertices is called the maximum nonseparating independent set.In this paper,we firstly give an upper bound for Z(G)of regular graphs and determine Z(G)for some types of circular graphs.Secondly,we show a relationship between Z(G)and the maximum genus M(G)of a general graph.Finally,an important formula is provided to compute Z(G),i.e.,Z(G)=Σx∈I dI(x)+2(M(G-I)-γM(G))+(ξ(G-I)-ξ(G));where I is the maximum nonseparating independent set and ξ(G)is the Betti deficiency(Xuong,1979)of G.

A TIGHT LOWER BOUND ON THE MAXIMUM GENUS OF 3-EDGE CONNECTED LOOPLESS GRAPHS

It is shown that the lower bound on the maximum genus of a 3-edge connected loopless graph is at least one-third of its cycle rank. Moreover, this lower bound is tight. There are infinitely such graphs attaining the bound.

A RELATIVE MAXIMUM GENUS GRAPH EMBEDDING AND ITS LOCAL MAXIMUM GENUS

A relative embedding of a connected graph is an embedding of the graph in some surface with respect to some closed walks, each of which bounds a face of the embedding. The relative maximum genus of a connected graph is the maximum of integer k with the property that the graph has a relative embedding in the orientable surface with k handles. A polynomial algorithm is provided for constructing relative maximum genus embedding of a graph of the relative tree of the graph is planar. Under this condition, just like maximum genus embedding, a graph does not have any locally strict maximum genus.

A POLYNOMIAL ALGORITHM FOR FINDING THEMINIMUM FEEDBACK VERTEX SET OF A3-REGULAR SIMPLE GRAPH

A subset of the vertex set of a graph is a feedback vertex set of the graph if the resulting graph is a forest after removed the vertex subset from the graph. A polynomial algorithm for finding a minimum feedback vertex set of a 3-regular simple graph is provided.

Minimum Genus Embeddings of the Complete Graph

In this paper, the problem of construction of exponentially many minimum genus crouchdings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding （or rotation） schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K12s＋8 in orientable surfaces, which show that there are at least 10/5 × （200/9）^s distinct minimum genus embeddings for K12s＋8 in orientable surfaces. We have also proved that K12s＋8 has at least 10/3× （200/9）^s distinct minimum genus embeddings in non-orientable surfaces.

Exponentially Many Genus Embeddings of the Complete Graph K_(12s+3)

In this paper, we consider the problem of construction of exponentially many distinct genus embeddings of complete graphs. There are three approaches to solve the problem. The first approach is to construct exponentially many current graphs by the theory of graceful labellings of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding（or rotation） scheme of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to these three approaches, we can construct exponentially many distinct genus embeddings of complete graph K12s＋3, which show that there are at least1/2× （200/9）s distinct genus embeddings for K12s＋3.

Up-embeddability via girth and the degree-sum of adjacent vertices

Let G be a simple graph of order n and girth g. For any two adjacent vertices u and v of G, if d G (u) + d G (v) ? n ? 2g + 5 then G is up-embeddable. In the case of 2-edge-connected (resp. 3-edge-connected) graph, G is up-embeddable if d G (u) + d G (v) ? n ? 2g + 3 (resp. d G (u) + d G (v) ? n ? 2g ?5) for any two adjacent vertices u and v of G. Furthermore, the above three lower bounds are all shown to be tight.

Fundamental cycles and graph embeddings

In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T, there exists a sequence of fundamental cycles C 1,C 2,…,C 2g with C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C 1, C 2,…,C 2γM(G) such that C 2i?1 ∩ C 2i ≠ /0 for 1 ? i ? γM (G), where β(G) and γM (G) are the Betti number and the maximum genus of G, respectively. This implies that it is possible to construct an orientable embedding with large genus of a graph G from an arbitrary spanning tree T (which may have very large number of odd components in G E(T)). This is different from the earlier work of Xuong and Liu, where spanning trees with small odd components are needed. In fact, this makes a common generalization of Xuong, Liu and Fu et al. Furthermore, we show that (1) this result is useful for locating the maximum genus of a graph having a specific edge-cut. Some known results for embedded graphs are also concluded; (2) the maximum genus problem may be reduced to the maximum matching problem. Based on this result and the algorithm of Micali-Vazirani, we present a new efficient algorithm to determine the maximum genus of a graph in $ O((\beta (G))^{\frac{5} {2}} ) $ steps. Our method is straight and quite different from the algorithm of Furst, Gross and McGeoch which depends on a result of Giles where matroid parity method is needed.

Up-embeddability of Graphs with New Degree-sum

Let G be a k（k ≤ 2）-edge connected simple graph with minimal degree ≥ 3 and girth g, r = [g-1/2]. For any edge uv ∈ E（G）, if dG（u） ＋ dG（v） 〉2v（G） - 2（k ＋ 1）（9 - 2r）/（k ＋ 1）（2r - 1）（g - 2r）＋ 2（g - 2r - 1）,then G is up-embeddable. Furthermore, similar results for 3-edge connected simple graphs are also obtained.