Distance-transitive dihedrants

The main result of this article is a classification of distance-transitive Cayley graphs on dihedral groups. We show that a Cayley graph X on a dihedral group is distance-transitive if and only if X is isomorphic to one of the following graphs: the complete graph K _2n ; a complete multipartite graph K _t×m with t anticliques of size m, where t m is even; the complete bipartite graph without 1-factor K _n,n − nK ₂; the cycle C _2n ; the incidence or the non-incidence graph of the projective geometry PG _d-1(d,q), d ≥ 2; the incidence or the non-incidence graph of a symmetric design on 11 vertices.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

4p阶二面体群连通3度Cayley有向图的正规性

设G是一个有限群,S是G的不包含单位元1的非空子集,定义群G关于S的Cayley(有向)图X:=Cay(G,S)如下:V(X)=G,E(X)={(g,sg)|g∈G,s∈S}.Cayley(有向)图X:=Cay(G,S)称为正规的,如果G的右正则表示R(G)在X的自同构群Aut(X)中是正规的.设G是4p阶二面体群(p为素数).考察了Cay(G,S)连通3度的正规性,并给出了这些图的全自同构群.     

4p阶二面体群的弱3-CI性

决定了4p(p是奇素数)阶二面体群的连通3度Cayley图的完全分类,并证明4p阶二面体群不是弱3-CI群,从而否定了C.H.Li关于"所有有限群都是弱3-CI群"的猜想     

Two sufficient conditions for non-normal Cayley graphs and their applications

A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in the full automorphism group of Cay(G, S). In this paper, two sufficient conditions for non-normal Cayley graphs are given and by using the conditions, five infinite families of connected non-normal Cayley graphs are constructed. As an application, all connected non-normal Cayley graphs of valency 5 on A5 are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A5 determined by Xu and Xu. Further, we classify all non-CI Cayley graphs of valency 5 on A5, while Xu et al. have proved that As is a 4-CI group.     

二面体群的小度数Cayley图的同构类的计数

设G是有限群,S是G的一个不包含单位元的非空子集且满足S^-1=S,定义群G关于S一个的Cayley图x=Cay(G,S)如下：V(X)=G,E(X)=｛(g,sg)｜g∈G,s∈S}.对于素数P,本文给出了2p阶的二面体群的3度和4度Cayley图的同构类的个数.     

On factor-invariant graphs

We classify trivalent vertex-transitive graphs whose edge sets have a partition into a Hamilton cycle and a 1-factor that is invariant under the action of the full automorphism group.     

Dihedral Hamiltonian Cycle Systems of the Cocktail Party Graph

The existence problem for a Hamiltonian cycle decomposition of (the so called cocktail party graph) with a dihedral automorphism group acting sharply transitively on the vertices is completely solved. Such Hamiltonian cycle decompositions exist for all even n while, for n odd, they exist if and only if the following conditions hold: (i) n is not a prime power; (ii) there is a suitable ? such that (mod 2^?) for all prime factors p of n and the number of the prime factors (counted with their respective multiplicities) such that (mod ) is even. Thus in particular one has a dihedral Hamiltonian cycle decomposition of the cocktail party graph on 8k vertices for all k, while it is known that no such cyclic Hamiltonian cycle decomposition exists. Finally, this paper touches on a recently introduced symmetry requirement by proving that there exists a dihedral and symmetric Hamiltonian cycle system of if and only if (mod 4).     

On constructing normal and non-normal Cayley graphs

Bamberg and Giudici (2011) showed that the point graphs of certain generalised quadrangles of order $(q?1,q+1)$, where $q=p^k$ is a prime power with $p\ge 5$, are both normal and non-normal Cayley graphs for two isomorphic groups. We call these graphs BG-graphs. In this paper, we show that the Cayley graphs obtained from a finite number of BG-graphs by Cartesian product, direct product, and strong product also possess the property of being normal and non-normal Cayley graphs for two isomorphic groups.     

On Cayley graphs of rectangular groups

In this paper, we first give a characterization of Cayley graphs of rectangular groups. Then, vertex-transitivity of Cayley graphs of rectangular groups is considered. Further, it is shown that Cayley graphs Cay(S,C) which are automorphism-vertex-transitive, are in fact Cayley graphs of rectangular groups, if the subsemigroup generated by C is an orthodox semigroup. Finally, a characterization of vertex-transitive graphs which are Cayley graphs of finite semigroups is concluded.     

Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111: 416–419]. We also generalizes an early result of M. Nánásiová and M. ?koviera [J. Algebraic Combin., 2009, 30: 103–110].     

On distance-regular Cayley graphs of generalized dicyclic groups

Let G be a generalized dicyclic group with identity 1. An inverse closed subset S of $G?\{1\}$ is called minimal if $〈S〉=G$ and there exists some $s\in S$ such that $〈S?\{s,s^{?1}\}〉\ne G$. In this paper, we characterize distance-regular Cayley graphs $\mathrm{Cay}(G,S)$ of G under the condition that S is minimal.     

Enumeration of cubic Cayley graphs on dihedral groups

Let p be an odd prime, and D_2p =<a, b|a^p = b² = 1, bab = a^-1 the dihedral group of order 2p. In this paper, we completely classify the cubic Cayley graphs on D_2p up to isomorphism by means of spectral method. By the way, we show that two cubic Cayley graphs on D_2p are isomorphic if and only if they are cospectral. Moreover, we obtain the number of isomorphic classes of cubic Cayley graphs on D_2p by using Gauss' celebrated law of quadratic reciprocity.     

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.     

4p~2阶4度半传递图

如果图X的全自同构群Aut(X)作用在其顶点集V(X)和边集E(X)上都是传递的,但作用在弧集Arc(X)上非传递,则称X是半传递图.研究了4p~2(p3且p≡-1(mod4))阶4度半传递图,确定了4p~2阶4度半传递图的连通性及其自同构群的阶.     

Graphically abelian groups

We define a group G to be graphically abelian if the function g?g⁻¹ induces an automorphism of every Cayley graph of G. We give equivalent characterizations of graphically abelian groups, note features of the adjacency matrices for Cayley graphs of graphically abelian groups, and show that a non-abelian group G is graphically abelian if and only if G=E×Q, where E is an elementary abelian 2-group and Q is a quaternion group.     

Tetravalent vertex‐transitive graphs of order 4p

A graph is vertex‐transitive if its automorphism group acts transitively on vertices of the graph. A vertex‐transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this article, the tetravalent vertex‐transitive non‐Cayley graphs of order 4p are classified for each prime p. As a result, there are one sporadic and five infinite families of such graphs, of which the sporadic one has order 20, and one infinite family exists for every prime p>3, two families exist if and only if p≡1 (mod 8) and the other two families exist if and only if p≡1 (mod 4). For each family there is a unique graph for a given order. © 2011 Wiley Periodicals, Inc.     

群与图的对称性

首先对平面图形的对称进行分析和利用其对称群进行量化,进而将此推广到考察一般图的广义"对称性"与图自同构群的关系,最后刻画了无平方因子阶局部本原弧传递图的自同构群结构.     

一类拟二面体群的四度Cayley图的正规性

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在AutX中正规.研究了4m阶拟二面体群G=a,b|a~(2m)=b~2=1,a~b=a~(m+1)的4度Cayley图的正规性,其中m=2~r,且r2,并得到拟二面体群的Cayley图的同构类型.