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.     

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.     

Cayley Digraphs of Finite Simple Groups with Small Out-Valency

Abstract

For a group G and a subset S of G which does not contain the identity of G, the Cayley digraph Cay(G, S) is called normal if R(G) is normal in Aut(Γ). In this paper, we investigate the normality of Cayley digraphs of finite simple groups with out-valency 2 and 3. We give several sufficient conditions for such Cayley digraphs to be normal. By using this result, we consider the digraphical regular representations of finite simple groups.     

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.     

The diameters of almost all Cayley digraphs

1.IntroductionLetGbeagroupandSasubsetofGnotcontainingtheidentity,1ofG.TheCayleydigraphofGwithrespecttoS,denotedbyX(G,S),isadigraphwhosevertexsetisGandforx,yEG,thereisanarcfromxtoyinX(G,S)ifandonlyifx--laES.IfS=S--',thenX(G,S)isactuallyagraphcalledCayleygraph.ThereisadiversityofliteratureonCnyleygraphsandCayleydigraphs.Themostlyinvestigatedsubjectsaretheconnectivityll'2],theHamiltonianpropertiesl3],theisomorphismsI4]andthediameterIS'6].Recelltly,someauthorsproposedtouseCayleygraph…     

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     

On finite groups with the cayley isomorphism property

Let G be a finite group, and let Cay(G, S) be a Cayley digraph of G. If, for all T ⊂ G, Cay(G, S) ≅ Cay(G, T) implies S^α = T for some α ∈ Aut(G), then Cay(G, S) is called a CI-graph of G. For a group G, if all Cayley digraphs of valency m are CI-graphs, then G is said to have the m-DCI property; if all Cayley graphs of valency m are CI-graphs, then G is said to have the m-CI property. It is shown that every finite group of order greater than 2 has a nontrivial CI-graph, and all finite groups with the m-CI property and with the m-DCI property are characterized for small values of m. A general investigation is made of the structure of Sylow subgroups of finite groups with the m-DCI property and with the m-CI property for large values of m. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 21–31, 1998     

On Isomorphisms of Minimal Cayley Graphs and Digraphs

 A Cayley graph or digraph Cay(G,S) is called a CI-graph of G if, for any T⊂G, Cay(G,S)≅Cay(G,T) if and only if S ^σ=T for some σ∈Aut(G). The aim of this paper is to characterize finite abelian groups for which all minimal Cayley graphs and digraphs are CI-graphs. Received: February 13, 1998 Final version received: May 7, 1999     

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     

Normal Cayley graphs of finite groups

LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ◃A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG≅ℤ₄×ℤ₂ orG≅Q ₈×ℤ ₂ ^r (r⩾0) and that every finite group has a normal Cayley digraph, where Z_m is the cyclic group of orderm and Q₈ is the quaternion group of order 8. Project supported by the National Natural Science Foundation of China (Grant No. 10231060) and the Doctorial Program Foundation of Institutions of Higher Education of China.     

Weak Cayley table groups III: PSL(2,q)

A weak Cayley table isomorphism is a bijection φ:G→H of groups such that φ(xy)～φ(x)φ(y) for all x,y∈G. Here ～ denotes conjugacy. When G = H the set of all weak Cayley table isomorphisms φ:G→G forms a group 𝒲(G) that contains the automorphism group Aut(G) and the inverse map I:G→G,x?x^?1. Let 𝒲₀(G) = ?Aut(G),I?≤𝒲(G) and say that G has trivial weak Cayley table group if 𝒲(G) = 𝒲₀(G). We show that PSL(2,pⁿ) has trivial weak Cayley table group, where p≥5 is a prime and n≥1.     

Unique ergodicity of flows on homogeneous spaces

LetG be a unimodular Lie group, Γ a co-compact discrete subgroup ofG and ‘a’ a semisimple element ofG. LetT _a be the mapgΓ →ag Γ:G/Γ →G/Γ. The following statements are pairwise equivalent: (1) (T _a, G/Γ,θ) is weak-mixing. (2) (T _a, G/Γ) is topologically weak-mixing. (3) (G ^u, G/Γ) is uniquely ergodic. (4) (G ^u, G/Γ,θ) is ergodic. (5) (G ^u, G/Γ) is point transitive. (6) (G ^u, G/Γ) is minimal. If in additionG is semisimple with finite center and no compact factors, then the statement “(T _a, G/Γ,θ) is ergodic” may be added to the above list. The authors were partially supported by NSF grant MCS 75-05250.     

Conjecture of Li and Praeger concerning the isomorphisms of Cayley graphs of A5

LetG be a finite group, andS a subset ofG \ |1| withS =S ⁻¹. We useX = Cay(G,S) to denote the Cayley graph ofG with respect toS. We callS a Cl-subset ofG, if for any isomorphism Cay(G,S) ≈ Cay(G,T) there is an α∈ Aut(G) such thatS ^α =T. Assume that m is a positive integer.G is called anm-Cl-group if every subsetS ofG withS =S ⁻¹ and | S | ≤m is Cl. In this paper we prove that the alternating groupA ₅ is a 4-Cl-group, which was a conjecture posed by Li and Praeger.     

Further restrictions on the structure of finite CI-groups

A group G is called a CI-group if, for any subsets S,T⊂ G, whenever two Cayley graphs Cay(G,S) and Cay(G,T) are isomorphic, there exists an element σ∊Aut(G) such that Sσ = T. The problem of seeking finite CI-groups is a long-standing open problem in the area of Cayley graphs. This paper contributes towards a complete classification of finite CI-groups. First it is shown that the Frobenius groups of order 4p and 6p, and the metacyclic groups of order 9p of which the centre has order 3 are not CI-groups, where p is an odd prime. Then a shorter explicit list is given of candidates for finite CI-groups. Finally, some new families of finite CI-groups are found, that is, the metacyclic groups of order 4p (with centre of order 2) and of order 8p (with centre of order 4) are CI-groups, and a proof is given for the Frobenius group of order 3p to be a CI-group, where p is a prime. C. H. Li was supported by an Australian Research Council Discovery Grant and a QEII Fellowship. Z. P. Lu was partially supported by the NNSF and TYYF of China. P. P. Pálfy was supported by the Hungarian Science Foundation (OTKA), grant no. T38059.     

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     

Cayley digraphs and lexicographic product

In this paper, we prove that a Cayley digraph Γ = Cay(G, S) is a nontrivial lexicographical product if and only if there is a nontrivial subgroup H of G such that S∖H is a union of some double cosets of H in G.      

On r-recognition by prime graph of Bp(3) where p is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then G @ B_p(3){G\cong B_p(3)} or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then G @ B₃(3), C₃(3), D₄(3){G\cong B_3(3), C_3(3), D_4(3)}, or G/O₂(G) @ Aut(²B₂(8)){G/O_2(G)\cong {\rm Aut}(^2B_2(8))}. As a corollary, the main result of the above paper is obtained.     

Expansion Of Product Replacement Graphs

We establish a connection between the expansion coefficient of the product replacement graph Γ_k(G) and the minimal expansion coefficient of a Cayley graph of G with k generators. In particular, we show that the product replacement graphs Γ_k(PSL(2,p)) form an expander family, under assumption that all Cayley graphs of PSL(2,p), with at most k generators are expanders. This gives a new explanation of the outstanding performance of the product replacement algorithm and supports the speculation that all product replacement graphs are expanders [42,52].     

Metric properties of the tropical Abel–Jacobi map

Let Γ be a tropical curve (or metric graph), and fix a base point p∈Γ. We define the Jacobian group J(G) of a finite weighted graph G, and show that the Jacobian J(Γ) is canonically isomorphic to the direct limit of J(G) over all weighted graph models G for Γ. This result is useful for reducing certain questions about the Abel–Jacobi map Φ _p :Γ→J(Γ), defined by Mikhalkin and Zharkov, to purely combinatorial questions about weighted graphs. We prove that J(G) is finite if and only if the edges in each 2-connected component of G are commensurable over ℚ. As an application of our direct limit theorem, we derive some local comparison formulas between ρ and \varPhi_p^*(r){\varPhi}_{p}^{*}(\rho) for three different natural “metrics” ρ on J(Γ). One of these formulas implies that Φ _p is a tropical isometry when Γ is 2-edge-connected. Another shows that the canonical measure μ _Zh on a metric graph Γ, defined by S. Zhang, measures lengths on Φ _p (Γ) with respect to the “sup-norm” on J(Γ).