Circulant Double Coverings of a Circulant Graph of Valency Five

Enumerating the isomorphism classes of several types of graph covering projections is one of the central research topics in enumerative topological graph theory. A covering of G is called circulant if its covering graph is circulant. Recently, the authors [Discrete Math., 277, 73-85 （2004）1 enumerated the isomorphism classes of circulant double coverings of a certain type, called a typical covering, and showed that no double covering of a circulant graph of valency three is circulant. Also, in [Graphs and Combinatorics, 21,386 400 （2005）], the isomorphism classes of circulant double coverings of a circulant graph of valency four are enumerated. In this paper, the isomorphism classes of circulant double coverings of a circulant graph of valency five are enumerated.     

Enumerating typical abelian prime-fold coverings of a circulant graph

Enumerating the isomorphism classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory (see [R. Feng, J.H. Kwak, J. Kim, J. Lee, Isomorphism classes of concrete graph coverings, SIAM J. Discrete Math. 11 (1998) 265-272; R. Feng, J.H. Kwak, Typical circulant double coverings of a circulant graph, Discrete Math. 277 (2004) 73-85; R. Feng, J.H. Kwak, Y.S. Kwon, Enumerating typical circulant covering projections onto a circulant graph, SIAM J. Discrete Math. 19 (2005) 196-207; SIAM J. Discrete Math. 21 (2007) 548-550 (erratum); M. Hofmeister, Graph covering projections arising from finite vector spaces over finite fields, Discrete Math. 143 (1995) 87-97; M. Hofmeister, Enumeration of concrete regular covering projections, SIAM J. Discrete Math. 8 (1995) 51-61; M. Hofmeister, A note on counting connected graph covering projections, SIAM J. Discrete Math. 11 (1998) 286-292; J.H. Kwak, J. Chun, J. Lee, Enumeration of regular graph coverings having finite abelian covering transformation groups, SIAM J. Discrete Math. 11 (1998) 273-285; J.H. Kwak, J. Lee, Isomorphism classes of graph bundles, Canad. J. Math. XLII (1990) 747-761]). A covering is called abelian (or circulant, respectively) if its covering graph is a Cayley graph on an abelian (or a cyclic, respectively) group. A covering p from a Cayley graph onto another Cay (Q,Y) is called typical if the map p:A→Q on the vertex sets is a group epimorphism. Recently, the isomorphism classes of connected typical circulant r-fold coverings of a circulant graph are enumerated in [R. Feng, J.H. Kwak, Typical circulant double coverings of a circulant graph, Discrete Math. 277 (2004) 73-85] for r=2 and in [R. Feng, J.H. Kwak, Y.S. Kwon, Enumerating typical circulant covering projections onto a circulant graph, SIAM J. Discrete Math. 19 (2005) 196-207; SIAM J. Discrete Math. 21 (2007) 548-550 (erratum)] for any r. As a continuation of these works, we enumerate in this paper the isomorphism classes of typical abelian prime-fold coverings of a circulant graph.     

On the Classification of Arc-transitive Circulant Digraphs of Order Odd-Prime-Squared

A Cayley graph F = Cay（G, S） of a group G with respect to S is called a circulant digraph of order pk if G is a cyclic group of the same order. Investigated in this paper are the normality conditions for arc-transitive circulant （di）graphs of order p^2 and the classification of all such graphs. It is proved that any connected arc-transitive circulant digraph of order p^2 is, up to a graph isomorphism, either Kp2, G（p^2,r）, or G（p,r）[pK1], where r｜p- 1.     

Arc-Transitive Cayley Graphs of Valency at Most Four on Abelian Groups

In this paper we give a complete classification for arc-transitive and one-regular Cayley graphs of valency at most four on finite abelian groups.AMS Subject Classifications: 05C25 20B25.This work was supported by the National Natural Science Foundation of China (proj. no. 19831050) and the Doctoral Program Foundation of Institutions of Higher Education of China (proj. no. 97000141).     

Petersen图的点传递正则覆盖图

运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 .     

Automorphisms of Maps with a Given Underlying Graph and Their Application to Enumeration

A graph is called a semi-regular graph if its automorphism group action on its ordered pair of adjacent vertices is semi-regular. In this paper, a necessary and sufficient condition for an automorphism of the graph F to be an automorphism of a map with the underlying graph F is obtained. Using this result, all orientation-preserving automorphisms of maps on surfaces (orientable and non-orientable) or just orientable surfaces with a given underlying semi-regular graph F are determined. Formulas for the numbers of non-equivalent embeddings of this kind of graphs on surfaces (orientable, non-orientable or both) are established, and especially, the non-equivalent embeddings of circulant graphs of a prime order on orientable, non-orientable and general surfaces are enumerated.     

END-正则的循环图

称图X是End-正则图如果它的自同态幺半解EndX是正则的幺半解，即关于任意自同态f存在一个自同态g使得fgf=f。本文对顶点度数小于4的End-正则循环图进行了刻划。     

On isomorphisms of circulant digraphs of bounded degree

C.H. Li recently made the following conjecture: Let Γ be a circulant digraph of order n=n₁n₂ and degree m, where gcd(n₁,n₂)=1, n₁ divides 4k, where k is odd and square-free, and every prime divisor of n₂ is greater than m, or, if Γ is a circulant graph, every prime divisor of n₂ is greater than 2m. Then Γ is a CI-digraph of Z_n. In this paper we verify that this conjecture is true.     

p~2阶弧传递循环图的正规性条件

群G关于S的有向Cayley图X=Cay(G,S)称为pk阶有向循环图,若G是pk阶循环群.利用有限群论和图论的较深刻的结果,对p2阶弧传递(有向)循环图的正规性条件进行了讨论,证明了任一p2阶弧传递(有向)循环图是正规的当且仅当(|Aut(G,S)|,p)=1.     

Enumerating Abelian Typical Cube-Free Fold Coverings of a Circulant Graph

Enumerating the isomorphism or equivalence classes of several types of graph coverings is one of the central research topics in enumerative topological graph theory.A covering projection p from a Cayley graph Cay(Г,X)onto another Cayley graph Cay(Q,y)is called typical if the function p:Г→Q on the vertex sets is a group epimorphism.A typical covering is called abelian(or circulant,respectively)if its covering graph is a Cayley graph on an abelism(or a cyclic,respectively)group.Recently,the equivalence classes of connected abelian typical prime-fold coverings of a circulant graph are enumerated.As a continuation of this work,we enumerate the equivalence classes of connected abelian typical cube-free fold coverings of a circulant graph.     

Schuster性质在循环图上的实现

第四届国际图论会议上提出的十大未解决问题之一:确定所有满足=G~2的图G,本文提供了一种在循环图上搜索具有=G~2性质的图G的方法,由此得到: 在C_n,在C_n中仅有C_(14)<1,4>和C_(14)<1,6>具有性质=G~2。     

On Symmetric Cayley Graphs of Valency Eleven

A Cayley graph Γ=Cay(G,S)is said to be normal if G is normal in Aut Γ.In this paper,we investigate the normality problem of the connected 11-valent symmetric Cayley graphs Γ of finite nonabelian simple groups G,where the vertex stabilizer Av is soluble for A=Aut Γ and v ∈ VΓ.We prove that either Γ is normal or G=A5,A10,A54,A274,A549 or A1099.Further,11-valent symmetric nonnormal Cayley graphs of A5,A54 and A274 are constructed.This provides some more examples of nonnormal 11-valent symmetric Cayley graphs of finite nonabelian simple groups after the first graph of this kind(of valency 11)was constructed by Fang,Ma and Wang in 2011.     

图的倍图与补倍图

计算机科学数据库的关系中遇到了可归为倍图或补倍图的参数和哈密顿圈的问题．对简单图C,如果V（D（G））：V（G）∪V（G′）E（D（G））=E（C）∪E（C″）U{vivj′｜vi∈V（G）,Vj′∈V（G′）且vivj∈E（G））那么,称D（C）是C的倍图,如果V（D（G））=V（C）∪V（G′）,E（D（C））：E（C）∪E（G′）∪{vivj′}vi∈V（G）,vj′∈V（G’）and vivj∈（G））,称D（C）是G的补倍图,这里G′是G的拷贝．本文研究了D（G）和D的色数,边色数,欧拉性,哈密顿性和提出了D（G） 的边色数是D（G）的最大度等公开问题．     

循环图能量的一个上界

本文讨论循环图的能量,得到循环图能量上界的一个估计值.进一步得到整循环图能量的两个计算公式.     

Coverings of Graphs and Maps, Orthogonality, and Eigenvectors

Lifts of graph and map automorphisms can be described in terms of voltage assignments that are, in a sense, compatible with the automorphisms. We show that compatibility of ordinary voltage assignments in Abelian groups is related to orthogonality in certain -modules. For cyclic groups, compatibility turns out to be equivalent with the existence of eigenvectors of certain matrices that are naturally associated with graph automorphisms. This allows for a great simplification in characterizing compatible voltage assignments and has applications in constructions of highly symmetric graphs and maps.     

The degree-diameter problem for circulant graphs of degrees 10 and 11

This paper considers the degree-diameter problem for undirected circulant graphs. For degrees 10 and 11, newly discovered families of circulant graphs of arbitrary diameter are presented which are largest known and are conjectured to be extremal. They are also the largest-known Abelian Cayley graphs of these degrees. For each such family, the order of every graph in the family is defined by a quintic polynomial function of the diameter which is specific to the family. The elements of the generating set for each graph are similarly defined by a set of polynomials in the diameter. The existence of the graphs in the degree 10 families has been proved for all diameters. These graphs are consistent with a conjecture on the order of extremal Abelian Cayley and circulant graphs of any degree and diameter.     

Domination in Generalized Cayley Graph of Commutative Rings

Let $R$ be a commutative ring with identity and $n$ be a natural number. The generalized Cayley graph of $R$, denoted by $Γ^n_R$, is the graph whose vertex set is $R^n$\{0} and two distinct vertices $X$ and $Y$ are adjacent if and only if there exists an $n×n$ lower triangular matrix $A$ over $R$ whose entries on the main diagonal are non-zero such that $AX^T=Y^T$ or $AY^T=X^T$, where for a matrix $B$, $B^T$ is the matrix transpose of $B$. In this paper, we give some basic properties of$Γ^n_R$ and we determine the domination parameters of$Γ^n_R$.     

Integral circulant graphs

In this note we characterize integral graphs among circulant graphs. It is conjectured that there are exactly 2^τ(n)-1 non-isomorphic integral circulant graphs on n vertices, where τ(n) is the number of divisors of n.     

开关图的几个代数性质

首先对开关图的自同构群进行了研究,随即讨论了它的点传递性,并得到Calyley图的开关图依然是Cayley图.