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.     

Power graphs of (non)orientable genus two

The power graph of a finite group is the graph whose vertex set is the group, two distinct elements being adjacent if one is a power of the other. In this article, we classify the finite groups whose power graphs have (non)orientable genus two.     

The minimal genus problem in rational surfaces CP~2#nCP~2

There are three key ingredients in the study of the minimal genus problem for rational surfaces CP2#nCP2: the generalized adjunction formula, the action of the orthogonal group of the Lorentz space and the geometric construction. In this paper, we prove the uniqueness of the standard form (see Definition 1.1 and Theorem 1.1) of a 2-dimensional homology class under the action of the subgroup of the Lorentz orthogonal group that is realized by the diffeomorphisms of CP2#nCP2.Using the geometric construction, we determine the minimal genera of some classes (see Theorem 1.2).     

The orientable genus of some joins of complete graphs with large edgeless graphs

In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with m≥n−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with m≥n−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when n is even and m≥n, the genus of when n=2^p+2 for p≥3 and m≥n−1, and the genus of when n=2^p+1 for p≥3 and m≥n+1. In all of these cases the genus is the same as the genus of K_m,n, namely ⌈(m−2)(n−2)/4⌉.     

Phase transitions in graphs on orientable surfaces

Let be the orientable surface of genus and denote by the class of all graphs on vertex set with edges embeddable on . We prove that the component structure of a graph chosen uniformly at random from features two phase transitions. The first phase transition mirrors the classical phase transition in the Erd?s‐Rényi random graph chosen uniformly at random from all graphs with vertex set and edges. It takes place at , when the giant component emerges. The second phase transition occurs at , when the giant component covers almost all vertices of the graph. This kind of phenomenon is strikingly different from and has only been observed for graphs on surfaces.     

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

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings 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 K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

Py-calabi quasi-morphisms and quasi-states on orientable surfaces of higher genus

We show that a Py-Calabi quasi-morphism on the group of Hamiltonian diffeomorphisms of surfaces of higher genus gives rise to a quasi-state.     

Isotopy-invariant topological measures on closed orientable surfaces of higher genus

Given a closed orientable surface Σ of genus at least two, we establish an affine isomorphism between the convex compact set of isotopy-invariant topological measures on Σ and the convex compact set of additive functions on the set of isotopy classes of certain subsurfaces of Σ. We then construct such additive functions, and thus isotopy-invariant topological measures, from probability measures on Σ together with some additional data. The map associating topological measures to probability measures is affine and continuous. Certain Dirac measures map to simple topological measures, while the topological measures due to Py and Rosenberg arise from the normalized Euler characteristic.     

The orientable genus is nonadditive

A graph G is a k-amalgamation of two graphs G₁ and G₂ if G = G₁ ∪ G₂ and G₁ ∩ G₂ is a set of k vertices. In this paper we construct 3-amalgamations G_n = H_n ∪ H_n such that γ(G_n) = 5n and γ(H_n) = 3n, where γ denotes the orientable genus of a graph. Thus γ(G₁ ∪ G₂) may differ from γ(G₁) + γ(G₂) by an arbitrarily large amount for amalgamations over 3 (or more) vertices. In contrast, an earlier paper shows that the nonorientable genus of a k-amalgamation differs from the sum of the nonorientable genera of its parts by at most a quadratic on k.     

Long cycles in 3‐connected graphs in orientable surfaces

In this article, we apply a cutting theorem of Thomassen to show that there is a function f: N → N such that if G is a 3‐connected graph on n vertices which can be embedded in the orientable surface of genus g with face‐width at least f(g), then G contains a cycle of length at least cn, where c is a constant not dependent on g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002     

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 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 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. This work was supported by the National Natural Science Foundation of China (Grant No. 10671073), Science and Technology commission of Shanghai Municipality (Grant No. 07XD14011) and Shanghai Leading Academic Discipline Project (Grant No. B407)     

Incompressible surfaces in handlebodies and closed 3-manifolds of Heegaard genus 2

In this paper, we shall prove that for any integer 0$">, 1) a handlebody of genus 2 contains a separating incompressible surface of genus , 2) there exists a closed 3-manifold of Heegaard genus which contains a separating incompressible surface of genus .

     

The Laplacian spectral radius of graphs on surfaces

Let G be an n-vertex (n?3) simple graph embeddable on a surface of Euler genus γ (the number of crosscaps plus twice the number of handles). Denote by Δ the maximum degree of G. In this paper, we first present two upper bounds on the Laplacian spectral radius of G as follows:

(i)

     

The nonorientable genus of the join of two cycles

In this paper, we show that the nonorientable genus of Cm ＋ Cn, the join of two cycles Cm and Cn, is equal to [（（m-2）（n-2））/2] if m = 3, n ≡ 1 （mod 2）, or m ≥ 4, n ≥ 4, （m, n） （4, 4）. We determine that the nonorientable genus of C4 ＋C4 is 3, and that the nonorientable genus of C3 ＋Cn is n/2 if n ≡ 0 （mod 2）. Our results show that a minimum nonorientable genus embedding of the complete bipartite graph Km,n cannot be extended to an embedding of the join of two cycles without increasing the genus of the surface.     

The directed genus of the de Bruijn graph

Define the directed genus, Γ(G), of an Eulerian digraph G to be the minimum value of p for which G has a 2-cell embedding in the orientable surface of genus p so that every face of the embedding is bounded by a directed circuit in G. The directed genus of the de Bruijn graph D_n is shown to be

     

The Erd?s-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces

We prove that for any orientable surface S and any non-negative integer k, there exists an integer f_S(k) such that every graph G embeddable in S has either k vertex-disjoint odd cycles or a vertex set A of cardinality at most f_S(k) such that G-A is bipartite. Such a property is called the Erd?s-Pósa property for odd cycles. We also show its edge version. As Reed [Mangoes and blueberries, Combinatorica 19 (1999) 267-296] pointed out, the Erd?s-Pósa property for odd cycles do not hold for all non-orientable surfaces.