Search

A Cayley digraph Cay (G , S) of a group G with respect to a subset S of G is called a CI-digraph if for every Cayley digraph Cay (G , T) isomorphic to Cay (G , S) , there exists an α ∈ Aut (G) such that S α = T . For a positive integer m, G is said to have the m-DCI property if all Cayley digraphs of G with out-valency m are CI-digraphs. Li (European J Combin 18:655–665, 1997) gave a necessary condition for cyclic groups to have the m-DCI property, and in this paper, we find a necessary condition for dihedral groups to have the m-DCI property. Let D 2 n be the dihedral group of order 2n, and assume that D 2 n has the m-DCI property for some 1 ≤ m ≤ n - 1 . It is shown that n is odd, and if further p + 1 ≤ m ≤ n - 1 for an odd prime divisor p of n, then p 2 ∤ n . Furthermore, if n is a power of a prime q, then D 2 n has the m-DCI property if and only if either n = q , or q is odd and 1 ≤ m ≤ q . [ABSTRACT FROM AUTHOR]

In this paper, we consider the possible types of regular maps of order 2 n , where the order of a regular map is the order of automorphism group of the map. For n ≤ 11 , M. Conder classified all regular maps of order 2 n . It is easy to classify regular maps of order 2 n whose valency or covalency is 2 or 2 n - 1 . So we assume that n ≥ 12 and 2 ≤ s , t ≤ n - 2 with s ≤ t to consider regular maps of order 2 n with type { 2 s , 2 t } . We show that for s + t ≤ n or for s + t > n with s = t , there exists a regular map of order 2 n with type { 2 s , 2 t } , and furthermore, we classify regular maps of order 2 n with types { 2 n - 2 , 2 n - 2 } and { 2 n - 3 , 2 n - 3 } . We conjecture that if s + t > n with s < t , then there is no regular map of order 2 n with type { 2 s , 2 t } , and we confirm the conjecture for t = n - 2 and n - 3 . [ABSTRACT FROM AUTHOR]

A Cayley (di)graph Cay (G , S) of a group G is called normal if the right regular representation of G is normal in the full automorphism group of Cay (G , S) , and a CI-(di)graph if for every Cayley (di)graph Cay (G , T) , Cay (G , S) ≅ Cay (G , T) implies that there is σ ∈ Aut (G) such that S σ = T. We call a group G an NDCI-group or NCI-group if all normal Cayley digraphs or graphs of G are CI-digraphs or CI-graphs, respectively. We prove that a cyclic group of order n is an NDCI-group if and only if 8 ∤ n , and an NCI-group if and only if either n = 8 or 8 ∤ n. [ABSTRACT FROM AUTHOR]

The (n,k)‐arrangement graph A(n,k) with 1≤k≤n−1, is the graph with vertex set the ordered k‐tuples of distinct elements in {1,2,...,n} and with two k‐tuples adjacent if they differ in exactly one of their coordinates. The (n,k)‐arrangement graph was proposed by Day and Tripathi in 1992, and is a widely studied interconnection network topology. The Johnson graph J(n,k) with 1≤k≤n−1, is the graph with vertex set the k‐element subsets of {1,2,...,n}, and with two k‐element subsets adjacent if their intersection has k−1 elements. In 1989, Brouwer, Cohen and Neumaier determined the automorphism group of J(n,k), and in 2015, Dobson and Malnič proved that J(n,k) a is Cayley graph if and only if (n,k)=(8,3), (32,3) or (n,2) with n≡3(mod4) being a prime‐power. In this article we prove that Aut(A(n,k))≅Sn×Sk, and as a byproduct, A(n,k) is a normal cover of J(n,k). Furthermore, A(n,k) is a Cayley graph if and only if (n,k)=(33,4), (11,4), (9,4), (12,5), (8,5), (9,6), (32,29), (33,30), (n,1), (n,n−1), (n,n−2), (q,2) or (q+1,3), where q is a prime‐power. Note that the graph A(n,n−1) is called the n‐star graph, and its automorphism group can be deduced from a general result given by Feng in 2006. In 1998, Chiang and Chen proved that A(n,n−2) is a Cayley graph on the alternating group An, and in 2011, Zhou determined the automorphism group of A(n,n−2). [ABSTRACT FROM AUTHOR]

In this paper, we characterize the finite groups 𝐺 of even order with the property that, for any involution 𝑥 and element 𝑦 of 𝐺, ⟨ x , y ⟩ is isomorphic to one of the following groups: Z2, Z22, Z4, Z6, Z2 × Z4, Z2 × Z6 and A4. As a result, a characterization will be obtained for the finite groups all of whose Cayley graphs of degree 3 have integral spectrum. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the asymptotic enumeration of bipartite Cayley digraphs and Cayley graphs over abelian groups. Let A be an abelian group and let ι be the automorphism of A defined by aι=a−1, for every a∈A. A Cayley graph Cay(A,S) is said to have an automorphism group as small as possible if Aut(Cay(A,S))=〈A,ι〉. In this paper, we show that, except for two infinite families, almost all bipartite Cayley graphs on abelian groups have automorphism group as small as possible. We also investigate the analogous question for bipartite Cayley digraphs. These results are used for the asymptotic enumeration of bipartite Cayley digraphs and graphs over abelian groups. [ABSTRACT FROM AUTHOR]

For each d ≥ 3 , n ≥ 5 , and k 1 , k 2 , ... , k d - 1 ≥ 2 with k 1 + k 2 + ⋯ + k d - 1 ≤ n - 1 , we show how to construct a regular d-polytope whose automorphism group is of order 2 n and whose Schläfli type is { 2 k 1 , 2 k 2 , ... , 2 k d - 1 } . [ABSTRACT FROM AUTHOR]

A Cayley graph of a group H is a finite simple graph Γ such that Aut (Γ) contains a subgroup isomorphic to H acting regularly on V (Γ) , while a Haar graph of H is a finite simple bipartite graph Σ such that Aut (Σ) contains a subgroup isomorphic to H acting semiregularly on V (Σ) and the H-orbits are equal to the bipartite sets of Σ . A Cayley graph is a Haar graph exactly when it is bipartite, but no simple condition is known for a Haar graph to be a Cayley graph. In this paper, we show that D 6 , D 8 , D 10 and Q 8 are the only finite inner abelian groups all of whose Haar graphs are Cayley graphs. (A group is called inner abelian if it is non-abelian, but all of its proper subgroups are abelian.) This result will then be used to derive that every non-solvable group admits a non-Cayley Haar graph. [ABSTRACT FROM AUTHOR]

Let G be a finite non-abelian simple group and let Γ be a connected tetravalent 2-arc-transitive G-regular graph. In 2004, Fang, Li, and Xu proved that either G is normal in the full automorphism group of Γ, or G is one of up to 22 exceptional candidates. In this paper, the number of exceptions is reduced to 7, and for each one, it is shown that has a normal arc-transitive non-abelian simple subgroup T such that and the pair (G, T) is explicitly given. Furthermore, there exists a G-regular -arc-transitive graph for each of the 7 pairs (G, T). [ABSTRACT FROM AUTHOR]

An m-Cayley graph Γ over a group G is defined as a graph which admits G as a semi-regular group of automorphisms with m orbits. This generalises the notions of a Cayley graph (where m = 1 ) and a bi-Cayley graph (where m = 2 ). The m-Cayley graph Γ over G is said to be normal if G is normal in the automorphism group Aut (Γ) of Γ , and core-free if the largest normal subgroup of Aut (Γ) contained in G is the identity subgroup. In this paper, we investigate properties of symmetric m-Cayley graphs in the special case of valency 3, and use these properties to develop a computational method for classifying connected cubic core-free symmetric m-Cayley graphs. We also prove that there is no 3-arc-transitive normal Cayley graph or bi-Cayley graph (with valency 3 or more), which answers a question posed by Li (Proc Amer Math Soc 133:31–41 2005). Using our classification method, we give a new proof of the fact that there are exactly 15 connected cubic core-free symmetric Cayley graphs, two of which are Cayley graphs over non-abelian simple groups. We also show that there are exactly 109 connected cubic core-free symmetric bi-Cayley graphs, 48 of which are bi-Cayley graphs over non-abelian simple groups, and that there are 1, 6, 81, 462 and 3267 connected cubic core-free 1-arc-regular 3-, 4-, 5-, 6- and 7-Cayley graphs, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we prove that for any positive integers n, s, t such that n ≥ 10, s , t ≥ 2 and n − 1 ≥ s + t, there exists a regular polytope with Schläfli type {2s, 2t} and its automorphism group is of order 2n. Furthermore, we classify regular polytopes with automorphism groups of order 2n and Schläfli types {4 , 2n−3}, {4, 2n−4} and {4, 2n−5}, therefore giving a partial answer to a problem proposed by Schulte and Weiss in [Problems on polytopes, their groups, and realizations, Period. Math. Hungar. 53 2006, 1–2, 231–255]. [ABSTRACT FROM AUTHOR]

A graph is said to be vertex-transitive non-Cayley if its full automorphism group acts transitively on its vertices and contains no subgroups acting regularly on its vertices. In this paper, a complete classification of cubic vertex-transitive non-Cayley graphs of order 12p, where p is a prime, is given. As a result, there are 11 sporadic and one infinite family of such graphs, of which the sporadic ones occur when p equals 5, 7 or 17, and the infinite family exists if and only if p ≡ 1 (mod 4), and in this family there is a unique graph for a given order. [ABSTRACT FROM AUTHOR]

The varietal hypercube graph $$VQ_n$$ ( $$n\ge 1$$ ) was proposed by Cheng and Chuang (Varietal hypercube-a new interconnection network topology for large scale multicomputer, Proceedings of the International Conference on Parallel and Distributed Systems, pp 703-708, 1994) as a topology for interconnection network that is an improvement over the well-known hypercube network. It was known that $$VQ_n$$ is a Cayley graph on the group $$D_4^s\times {{\mathbb {Z}}}_2^t$$ , where $$n=3s+t$$ with $$s\ge 0$$ and $$0\le t\le 2$$ . In the present paper, we prove that the full automorphism group of the varietal hypercube graph $$VQ_n$$ is $$(D_4^s\times {{\mathbb {Z}}}_2^t) \rtimes (({\mathbb {Z}}_{2}\wr S_s)\times S_t)$$ . An open problem in the literature is to determine whether a given Cayley graph is normal and the result shows that the varietal hypercube graph $$VQ_n$$ is a normal Cayley graph on the group $$D_4^s\times {{\mathbb {Z}}}_2^t$$ . [ABSTRACT FROM AUTHOR]

The balanced hypercube BHn, proposed by Wu and Huang, is a new variation of hypercube. A Hamiltonian bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path between two arbitrary vertices from different partite sets. A Hamiltonian laceable graph G is strongly Hamiltonian laceable if there is a path of length between any two distinct vertices of the same partite set. A graph G is called k-edge-fault strong Hamiltonian laceable, if G - F is strong Hamiltonian laceable for any edge-fault set F with . It has been proved that the balanced hypercube BHn is strong Hamiltonian laceable. In this paper, we improve the above result and prove that BHn is ( n - 1)-edge-fault strong Hamiltonian laceable. [ABSTRACT FROM AUTHOR]

Let Fv (resp. Fe) be the set of faulty vertices (resp. faulty edges) in the n-dimensional balanced hypercube BHn. The edge-bipancyclicity of BHn − Fv for | Fv| ≤ n − 1 had been proved in [Inform. Sci. 288 (2014) 449-461]. The existence of edge-Hamiltonian cycles in BHn − Fe for | Fe| ≤ 2 n − 2 were obtained in [ Appl. Math. Comput. 244 (2014) 447-456]. In this paper, we consider fault-tolerant cycle embedding of BHn with both faulty vertices and faulty edges, and prove that there exists a fault-free cycle of length 22 n − 2| Fv| in BHn with | Fv| + | Fe| ≤ 2 n − 3 and | Fv| ≤ n − 1 for n ≥ 2. [ABSTRACT FROM AUTHOR]

A regular cover of a connected graph is called dihedral or cyclic if its transformation group is dihedral or cyclic, respectively. Let X be a connected cubic symmetric graph of order 2 p for a prime p. Several publications have investigated the classification of edge-transitive dihedral or cyclic covers of X for specific p. The edge-transitive dihedral covers of X have been classified for p=2 and the edge-transitive cyclic covers of X have been classified for p≤5. In this paper an extension of the above results to an arbitrary prime p is presented. [ABSTRACT FROM AUTHOR]

A graph is edge-primitive if its automorphism group acts primitively on edges. Weiss (in J. Comb. Theory Ser. B 15, 269-288, ) determined edge-primitive cubic graphs. In this paper, we classify edge-primitive pentavalent graphs. The same classification of those of valency 4 is also done. [ABSTRACT FROM AUTHOR]

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super- λ, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In Z. Zhang, B. Wang (Super cyclically edge-connected transitive graphs, J. Combin. Optim. 22:549-562, ), it is proved that a connected edge-transitive graph is super- λ if either G is cubic with girth at least 7 or G has minimum degree at least 4 and girth at least 6, and the authors also conjectured that a connected graph which is both vertex-transitive and edge-transitive is always super cyclically edge-connected. In this article, for a λ-optimal but not super- λ graph G, all possible λ-superatoms of G which have non-empty intersection with other λ-superatoms are determined. This is then used to give a complete classification of non-super- λ edge-transitive k( k≥3)-regular graphs. [ABSTRACT FROM AUTHOR]

Let (A_n) be the alternating group of degree (n) with (n\ge 3). Set (S=\(1 2 i), (1 i 2) \vert 3\le i\le n\). The alternating group graph, denoted by $(AG_n)$, is defined as the Cayley graph on $(A_n)$ with respect to $(S)$. Jwo et al. [Networks 23 (1993) 315-326] introduced alternating group graph $(AG_n)$ as an interconnection network topology for computing systems. Conditional diagnosability, a new measure of diagnosability introduced by Lai et al. [IEEE Transactions on Computers 54(2) (2005) 165-175] can better measure the diagnosability of regular interconnection networks. This paper determines that under PMC-model the conditional diagnosability of $(AG_n)$ is 4 for $(n=4)$ and $(6n-18)$ for each $(n\ge 5)$. [ABSTRACT FROM PUBLISHER]

A graph is arc-regular if its automorphism group acts sharply-transitively on the set of its ordered edges. This paper answers an open question about the existence of arc-regular 3-valent graphs of order 4 m where m is an odd integer. Using the Gorenstein-Walter theorem, it is shown that any such graph must be a normal cover of a base graph, where the base graph has an arc-regular group of automorphisms that is isomorphic to a subgroup of Aut(PSL(2, q)) containing PSL(2, q) for some odd prime-power q. Also a construction is given for infinitely many such graphs-namely a family of Cayley graphs for the groups PSL(2, p) where p is an odd prime; the smallest of these has order 9828. [ABSTRACT FROM AUTHOR]

graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let p and q be primes. It is known that no tetravalent half-arc-transitive graphs of order 2 p exist and a tetravalent half-arc-transitive graph of order 4 p must be non-Cayley; such a non-Cayley graph exists if and only if p−1 is divisible by 8 and it is unique for a given order. Based on the constructions of tetravalent half-arc-transitive graphs given by Marušič (J. Comb. Theory B 73:41-76, ), in this paper the connected tetravalent half-arc-transitive graphs of order 2 pq are classified for distinct odd primes p and q. [ABSTRACT FROM AUTHOR]

Let Γ be a graph and let G be a vertex-transitive subgroup of the full automorphism group Aut(Γ) of Γ. The graph Γ is called G-normal if G is normal in Aut(Γ). In particular, a Cayley graph Cay(G, S) on a group G with respect to S is normal if the Cayley graph is R(G)-normal, where R(G) is the right regular representation of G. Let T be a non-abelian simple group and let G = Tℓ with ℓ ≥ 1. We prove that if every connected T-vertex-transitive cubic symmetric graph is T-normal, then every connected G-vertex-transitive cubic symmetric graph is G-normal. This result, among others, implies that a connected cubic symmetric Cayley graph on G is normal except for T ≅ A47 and a connected cubic G-symmetric graph is G-normal except for T ≅ A7, A15 or PSL(4, 2). [ABSTRACT FROM AUTHOR]

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 A 5 are determined, which generalizes a result about the normality of Cayley graphs of valency 3 or 4 on A 5 determined by Xu and Xu. Further, we classify all non-CI Cayley graphs of valency 5 on A 5, while Xu et al. have proved that A 5 is a 4-CI group. [ABSTRACT FROM AUTHOR]

Let AG ( n ,&Fopf; q ) be the n -dimensional affine space over &Fopf; q . For a given integer m with 0 ≤ m ≤ n , all m -flats form an orbit, denoted by &Mellintrf;( m , n ), under the action of the affine group AGL n (&Fopf; q ) of AG ( n ,&Fopf; q ). Denote the set of all intersections of m -flats in &Mellintrf;( m , n ) by ℒ( m , n ). By ordering ℒ( m , n ) by ordinary or reverse inclusion, two classes of lattices are obtained. This article discusses their geometricity, and computes their character polynomials. [ABSTRACT FROM AUTHOR]

Let X be a 4-valent connected vertex-transitive graph with odd-prime-power order p k ( k≥1), and let A be the full automorphism group of X. In this paper, we prove that the stabilizer A v of a vertex v in A is a 2-group if p ≠ 5, or a {2,3}-group if p = 5. Furthermore, if p = 5 | A v | is not divisible by 32. As a result, we show that any 4-valent connected vertex-transitive graph with odd-prime-power order p k ( k≥1) is at most 1-arc-transitive for p ≠ 5 and 2-arc-transitive for p = 5. [ABSTRACT FROM AUTHOR]

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≅ [2 K 1] with n>1, Aut( X) ≅ Z 2wr Z 2n, and either G=Z 2n+1=< a> and S={ a, a 2n+1}, or G=Z 2n× Z 2=< a>×< b> and S={ a, ab}. [ABSTRACT FROM AUTHOR]

Abstract We call a Cayley digraph GAMMA = Cay(G, S) normal for G if G[sub R], the right regular representation of G, is a normal subgroup of the full automorphism group Aut(GAMMA) of GAMMA. In this paper we determine the normality of Cayley digraphs of valency 2 on nonabelian groups of order 2p[sup 2] (p odd prime). As a result, a family of nonnormal Cayley digraphs is found. [ABSTRACT FROM AUTHOR]