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.     

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.     

Commutative rings with genus two annihilator graphs

Let R be a commutative ring and Z(R)* be its set of all nonzero zero-divisors. The annihilator graph of a commutative ring R is the simple undirected graph AG(R) with vertices Z(R)*, and two distinct vertices x and y are adjacent if and only if ann(xy)≠ann(x)∪ann(y). The notion of annihilator graph has been introduced and studied by Badawi [8 Badawi, A. (2014). On the annihilator graph of a commutative ring. Commun. Algebra 42(1):108–121.[Taylor &; Francis Online], [Web of Science ®] , [Google Scholar]]. In this paper, we classify the finite commutative rings whose AG(R) are projective. Also we determine all isomorphism classes of finite commutative rings with identity whose AG(R) has genus two.     

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⌉.     

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)     

On cyclically orientable graphs

Graph G is called cyclically orientable (CO) if it admits an orientation in which every simple chordless cycle is cyclically oriented. This family of graphs was introduced by Barot et al. [Cluster algebras of finite type and positive symmetrizable matrices, J. London Math. Soc. (3) 73 (2006) 545-564]. The authors obtained several nice characterizations of CO-graphs, being motivated primarily by their applications in cluster algebras. Here we obtain several new characterizations that provide algorithms for recognizing CO-graphs and obtaining their cyclic orientations in linear time. We show that the edge maximal CO-graphs are 2-trees; that is, G=(V,E) is a 2-tree if and only if G is CO and G^′=(V,E^′) is not CO whenever E is a proper subset of E^′.     

Regular orientable embeddings of complete bipartite graphs

In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph K_n,n are in one‐to‐one correspondence with the permutations on n elements satisfying a given criterion, and the isomorphism classes of them are completely classified when n is a product of any two (not necessarily distinct) prime numbers. For other n, a lower bound of the number of those isomorphism classes of K_n,n is obtained. As a result, many new regular orientable embeddings of the complete bipartite graph are constructed giving an answer of Nedela‐?koviera's question raised in 12 . © 2005 Wiley Periodicals, Inc. J Graph Theory     

Some results on diameters of Cayley graphs

In this note we obtain a simple expression of any finite group by means of its generating set. Applying this result we partly solve a conjecture on diameters of Cayley graphs proposed by Babai and Seress. We also obtain some other conclusions on diameters on Cayley graphs.     

A tight lower bound on the maximum genus of 3-edge connected loopless graphs

1.IntroductionThernchmumgenusl7M(G),ofacormectedgraphG~(V,E)isthem~amongthegenera,amongwhichGhasacellularembeddingonaspherewithkhandles.SinceanyembeddingofGhasatleastonefaCe,byEulerpolyhedralequation,itcanbeobtainedthatwhereP(G)=IE(G)I--IV(G)l IisthecyclerankofG.AgraphGiscalledop-imbeddableif7M(C)=Lop]exactly.Kund.[1]provedthatthereareatleasttWOedge-disjointspanningtreesinGifGis4-edgecormected.LiuandXuongcharacterizedtheuptheeddabilityofgraphsasinthefollowing.Theorem1.112'31.Acorm…     

A note on the automorphism groups of cubic Cayley graphs of finite simple groups

For a finite group G, a Cayley graph on G is said to be normal if . In this note, we prove that connected cubic non-symmetric Cayley graphs of the ten finite non-abelian simple groups G in the list of non-normal candidates given in [X.G. Fang, C.H. Li, J. Wang, M.Y. Xu, On cubic Cayley graphs of finite simple groups, Discrete Math. 244 (2002) 67-75] are normal.     

Commuting graphs of groups and related numerical parameters

Given a finite group G, we denote by Δ(G) the commuting graph of G which is defined as follows: the vertex set is G and two distinct vertices x and y are joined by an edge if and only if xy = yx. Clearly, Δ(G) is always connected for any group G. We denote by κ(G) the number of spanning trees of Δ(G). In the present paper, among other results, we first obtain the value κ(G) for some specific groups G, such as Frobenius groups, Dihedral groups, AC-groups, etc. Next, we characterize the alternating group A₅, in the class of nonsolvable groups through its tree-number κ(A₅). Finally, we classify the finite groups for which the power graph and the commuting graph coincide.     

The decycling number and maximum genus of cubic graphs

Let and denote the minimum size of a decycling set and maximum genus of a graph G, respectively. For a connected cubic graph G of order n, it is shown that . Applying the formula, we obtain some new results on the decycling number and maximum genus of cubic graphs. Furthermore, it is shown that the number of vertices of a decycling set S in a k‐regular graph G is , where c and are the number of components of and the number of edges in , respectively. Therefore, S is minimum if and only if is minimum. As an application, this leads to a lower bound for of a k‐regular graph G. In many cases this bound may be sharp.     

Results of the maximum genus of graphs

In this paper,we provide a new class of up-embeddable graphs,and obtain a tight lower bound on the maximum genus of a class of 2-connected pseudographs of diameter 2 and of a class of diameter 4 multi-graphs.This extends a result of Skoviera.     

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.     

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.     

A class of finite groups with complete character degree graphs

In this paper, we construct a new class of finite groups whose common divisor graphs are complete graphs, while there is no prime dividing all the nontrivial degrees.     

On the genus distributions of wheels and of related graphs

We are concerned with families of graphs in which there is a single root-vertex ofunbounded valence, and in which, however, there is a uniform upper bound for the valences of all the other vertices. Using a result of Zagier, we obtain formulas and recursions for the genus distributions of several such families, including the wheel graphs. We show that the region distribution of a wheel graph is approximately proportional to the sequence of Stirling numbers of the first kind. Stahl has previously obtained such a result for embeddings in surfaces whose genus is relatively near to the maximum genus. Here, we generalize Stahl’s result to the entire genus distributions of wheels. Moreover, we derive the genus distributions for four other graph families that have some similarities to wheels.