2^n和2p^2阶群上Cayley图的Hamilton图的分解

主要给出几类非交换群对Alspach猜想（当Cay（G,S）的度小于等于4时）成立,进一步对2n和2p2阶群Cayley图的Hamilton圈的分解进行了讨论.     

2n和2p2阶群上Cayley图的Hamilton图的分解

主要给出几类非交换群对Alspach猜想(当Cay(G,S)的度小于等于4时)成立,进一步对2n和2p2阶群Cayley图的Hamilton圈的分解进行了讨论.     

On Cayley digraphs on nonisomorphic 2‐groups

A necessary and sufficient condition is given for two Cayley digraphs X₁ = Cay(G₁, S₁) and X₂ = Cay(G₂, S₂) to be isomorphic, where the groups G_i are nonisomorphic abelian 2‐groups, and the digraphs X_i have a regular cyclic group of automorphisms. Our result extends that of Morris [J Graph Theory 3 (1999), 345–362] concerning p‐groups G_i, where p is an odd prime. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

On the Normality of Cayley Digraphs of Valency 2 on Non-Abelian Group of Odd Order

In this paper, we prove that the Cayley digraph = Cay(G, S) of valency 2 on non-abelian group G of odd order is normal if the automorphism group of A(), a graph constructed from by using the method presented in the paper, is primitive on the vertices set V(A(). We also prove that the Cayley digraphs of valency 2 on non-abelian group of order pq² are normal, where p and q are distinct odd primes.AMS Subject Classification (2000) 05C25 20B25Supported by the National Natural Science Foundation of China (Grant no. 19971086) and the Doctoral Program Foundation of the National Education Department of China.     

正圆有向图中的弧不相交的Hamilton路和圈

2012年,Bang-Jensen和Huang(J.Combin.Theory Ser.B.2012,102:701-714)证明了2-弧强的局部半完全有向图可以分解为两个弧不相交的强连通生成子图当且仅当D不是偶圈的二次幂,并提出了任意3-强的局部竞赛图中包含两个弧不相交的Hamilton圈的猜想.主要研究正圆有向图中的弧不相交的Hamilton路和Hamilton圈,并证明了任意3-弧强的正圆有向图中包含两个弧不相交的Hamilton圈和任意4-弧强的正圆有向图中包含一个Hamilton圈和两个Hamilton路,使得它们两两弧不相交.由于任意圆有向图一定是正圆有向图,所得结论可以推广到圆有向图中.又由于圆有向图是局部竞赛图的子图类,因此所得结论说明对局部竞赛图的子图类――圆有向图,Bang-Jensen和Huang的猜想成立.     

Connected graphs as subgraphs of Cayley graphs: Conditions on Hamiltonicity

Let Γ be a connected simple graph, let V(Γ) and E(Γ) denote the vertex-set and the edge-set of Γ, respectively, and let n=|V(Γ)|. For 1≤i≤n, let e_i be the element of elementary abelian group which has 1 in the ith coordinate, and 0 in all other coordinates. Assume that V(Γ)={e_i∣1≤i≤n}. We define a set Ω by Ω={e_i+e_j∣{e_i,e_j}∈E(Γ)}, and let Cay_Γ denote the Cayley graph over with respect to Ω. It turns out that Cay_Γ contains Γ as an isometric subgraph. In this paper, the relations between the spectra of Γ and Cay_Γ are discussed. Some conditions on the existence of Hamilton paths and cycles in Γ are obtained.     

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n‐HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is weakly n‐HP‐extendable if it contains a path of length n and if every such path is contained in some Hamilton path of Γ. Moreover, Γ is strongly n‐HP‐extendable if it contains a path of length n and if for every such path P there is a Hamilton path of Γ starting with P. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2‐HC‐extendable and a complete classification of 3‐HC‐extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4‐HP‐extendable. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

Planarity of Cayley graphs of graph products of groups

We obtain a complete classification of graph products of finite abelian groups whose Cayley graphs with respect to the standard presentations are planar.     

Isomorphic factorization of the complete graph into Cayley digraphs

Let Z_p denote the cyclic group of order p where p is a prime number. Let X = X(Z_p, H) denote the Cayley digraph of Z_p with respect to the symbol H. We obtain a necessary and sufficient condition on H so that the complete graph on p vertices can be edge‐partitioned into three copies of Cayley digraphs of the same group Z_p each isomorphic to X. Based on this condition on H, we then enumerate all such Cayley graphs and digraphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 243–256, 2006     

Hamilton cycles and paths in vertex-transitive graphs—Current directions

In this article current directions in solving Lovász’s problem about the existence of Hamilton cycles and paths in connected vertex-transitive graphs are given.     

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度的正规性,并给出了这些图的全自同构群.     

Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes

In this paper, we extend known relationships between Cayley digraphs and their subgraphs and coset graphs with respect to subgroups to obtain a number of general results on homomorphism between them. Intuitively, our results correspond to synthesizing alternative, more economical, interconnection networks by reducing the number of dimensions and/or link density of existing networks via mapping and pruning. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes, including the derivation of provably correct shortest-path routing algorithms for such networks.     

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.     

Automorphism Groups of 2-Valent Connected Cayley Digraphs on Regular <Emphasis Type="Italic">p</Emphasis>-Groups

 Let X=Cay(G,S) be a 2-valent connected Cayley digraph of a regular p-group G and let G _R be the right regular representation of G. It is proved that if G _R is not normal in Aut(X) then X≅[2K ₁ ] with n>1, Aut(X) ≅Z ₂ wrZ _2n , and either G=Z _2n+1 =<a> and S={a,a ²ⁿ⁺¹ }, or G=Z _2n ×Z ₂ =<a>×<b> and S={a,ab}. Received: May 26, 1999 Final version received: June 19, 2000     

The exponent of the primitive Cayley digraphs on finite Abelian groups

Let G be finite group and let S be a subset of G. We prove a necessary and sufficient condition for the Cayley digraph X_{(G, S)} to be primitive when S contains the central elements of G. As an immediate consequence we obtain that a Cayley digraph X_{(G, S)} on an Abelian group is primitive if and only if S^−1S is a generating set for G. Moreover, it is shown that if a Cayley digraph X_{(G, S)} on an Abelian group is primitive, then its exponent either is or is not exceeding . Finally, we also characterize those Cayley digraphs on Abelian groups with exponent . In particular, we generalize a number of well-known results for the primitive circulant matrices.     

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.     

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.