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.

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.

Maximum Genus of Strong Embeddings

The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover. Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.

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.

STRONG EMBEDDING OF HP-GRAPHS ON SURFACE WITH HIGHER GENUS

In 1990, Bondy posed the small circuit double cover （SCDC） conjecture： Every 2-connected graph has a circuit double cover （CDC） with the number of circuits less than ｜v｜ （the order of the vertex set V）. The strong embedding conjecture states that every 2-connected graph has a strong embedding on some surface in which the boundary of each face is a circuit. In this paper, HP-graph is defined as the graph which has a strong embedding on the projective plane with one face of valence ｜V｜ and the other faces of valence 3. And it is proved that the HP-graph has a strong embedding with ｜V｜ - 1 or less faces on some surface, which confirms both the SCDC conjecture and the strong embedding conjecture.

The genus polynomials of cross-ladder digraphs in orientable surfaces

Some results about the genus distributions of graphs are known,but little is known about those of digraphs.In this paper,the method of joint trees initiated by Liu is generalized to compute the embedding genus distributions of digraphs in orientable surfaces.The genus polynomials for a new kind of 4-regular digraphs called the cross-ladders in orientable surfaces are obtained.These results are close to solving the third problem given by Bonnington et al.

The genus distributions for a certain type of permutation graphs in orientable surfaces

A circuit is a connected nontrivial 2-regular graph. A graph G is a permutation graph over a circuit C, if G can be obtained from two copies of C by joining these two copies with a perfect matching. In this paper, based on the joint tree method introduced by Liu, the genus polynomials for a certain type of permutation graphs in orientable surfaces are given.

Genus Distributions of M(o|¨)bius Ladders

The genus distribution of a graph is a polynomial whose coefficients are the partition of the number of embeddings with respect to the genera. In this paper, the genus distribution of Mobius ladders is provided which is an infinite class of 3-connected simple graphs.

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.

The genus of a type of graph

Based on the joint tree model introduced by Liu, the genera of further types of graphs not necessary to have certain symmetry can be obtained. In this paper, we obtain the genus of a new type of graph with weak symmetry. As a corollary, the genus of complete tripartite graph K n,n,l (l≥n≥2) is also derived. The method used here is more direct than those methods, such as current graph, used to calculate the genus of a graph and can be realized in polynomial time.

Partial-dual Euler-genus polynomials for two classes of bouquets

[European J.Combin.,2020,86:Paper No.103084,20 pp.]introduced the concept of partial-dual Euler-genus polynomial in the ribbon graphs and gave the interpolation conjecture.That is,the partial-dual Euler-genus polynomial for any non-orientable ribbon graph is interpolating.In fact,[European J.Combin.,2022,102:Paper No.103493,7 pp.]gave two classes of counterexamples to deny the conjecture,and only one or two of the side loops contained in the two classes of bouquets were non-orientable.On the basis of[European J.Combin.,2022,102:Paper No.103493,7 pp.],we further calculate the partial-dual Euler-genus polynomials of two other classes of bouquets.One is non-interpolating,whose side loop has an arbitrary number of non-orientable loops.The other is interpolating,whose side loop has an arbitrary number of both non-orientable loops and orientable loops.

Genus distribution of ladder type and cross type graphs

In this paper a method is given to calculate the explicit expressions of embedding genus distribution for ladder type graphs and cross type graphs. As an example, we refind the genus distri- bution of the graph Jn which is the first class of graphs studied for genus distribution where its genus depends on n.

Genus Polynomials of Cycles with Double Edges

Two cellular embeddings i ： G→S and j ： G → S of a connected graph G into a closed orientable surface S are equivalent if there is an orientation-preserving surface homeomorphism h ： S → S such that hi = j. The genus polynomial of a graph G is defined by g[G]（x）=∞∑g=0agx^g, where ag is the number of equivalence classes of embeddings of G into the orientable surface Sg with g genera. In this paper, we compute the genus polynomial of a graph obtained from a cycle by replacing each edge by two multiple edges.

Genus Distributions for Several Types of Ladder-class Graphs

Calculating the genus distributions of ladder graphs is a concerned topic in topological graph theory.In this paper,we formulate several ladder-class graphs by using a starting graph iterative amalgamation with copies of a path to construct a base graph and then adding some edges to the appointed root-vertices of the base graph.By means of transfer matrix and a finer partition of the embeddings,the explicit formulas for the genus distribution polynomials of four types of ladder-class graphs are derived.

LOWER BOUND NUMBER OF IRREDUCIBLE GRAPHS ON SURMCES

Irreducible graphs are those graphs which can hot be embedded on some surface but deleting ally edge of this graph, the resultant graph can be embedded on the surface. This paper characterizes one kind of irreducible graphs and it is shown that the lower bound number of irreducible graphs for the surface of genus n is 2 × 16n.

Some Open Problems in Geometric Topologyof Low Dimensions

ＳｏｍｅＯｐｅｎＰｒｏｂｌｅｍｓｉｎＧｅｏｍｅｔｒｉｃＴｏｐｏｌｏｇｙｏｆＬｏｗＤｉｍｅｎｓｉｏｎｓ￥ＡｌｂｅｒｔｏＣＡＶＩＣＣＨＩＯＬＩ（ＤｅｐａｒｔｍｅｎｔＯｆＭａｔｈｅｍａｔｉｃｓ，ＵｎｉｖｅｒｓｉｔｙｏｆＭｏｄｅｎａ，ＶｉａＣａｍｐｉ２１３／...

Branched Coverings and Embedded Surfaces in Four-manifolds

In this paper, we get a lower bound on the genera of surfaces re, presenting certain divisible classes in some 4-manifold X with Hi（X; Z） finite.

A Note on Directed Genera of Some Tournaments

An embedding of a digraph in an orientable surface is an embedding as the underlying graph and arcs in each region force a directed cycle. The directed genus is the minimum genus of surfaces in which the digraph can be directed embedded. Bonnington, Conder, Morton and McKenna [J. Cornbin. Theory Ser. B,85（2002） 1-20] gave the problem that which tournaments on n vertices have the directed genus [（n-3）（n-4）/12]the genus of Kn. In this paper, we use the current graph method to show that there exists a tournament, whichhas the directed genus[（n-3）（n-4）/12], on n vertices if and only if n = 3 or 7 （mod 12）.

Genera of Cayley maps

The genus distribution of a graph G is defined to be the sequence {gm}, where gm is the number of different embeddings of G in the closed orientable surface of genus m. In this paper, we examine the genus distributions of Cayley maps for several Cayley graphs. It will be shown that the genus distribution of Cayley maps has many different properties from its usual genus distribution.