Edge-forwarding index of star graphs and other Cayley graphs

We present a technique for building, in some Cayley graphs, a routing for which the load of every edge is almost the same. This technique enables us to find the edge-forwarding index of star graphs and complete-transposition graphs.     

Large butterfly Cayley graphs and digraphs

We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large $k$ and for values of $d$ taken from a large interval, the largest known Cayley graphs and digraphs of diameter $k$ and degree $d$. Another method yields, for sufficiently large $k$ and infinitely many values of $d$, Cayley graphs and digraphs of diameter $k$ and degree $d$ whose order is exponentially larger in $k$ than any previously constructed. In the directed case, these are within a linear factor in $k$ of the Moore bound.     

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.      

Isomorphic Cayley graphs on nonisomorphic groups

The issue of when two Cayley digraphs on different abelian groups of prime power order can be isomorphic is examined. This had previously been determined by Anne Joseph for squares of primes; her results are extended. © 1999 John Wiley & Sons, Inc. J Graph Theory 3: 345–362, 1999     

On WL-rank of Deza Cayley graphs

The WL-rank of a graph Γ is defined to be the rank of the coherent configuration of Γ. We construct a new infinite family of strictly Deza Cayley graphs for which the WL-rank is equal to the number of vertices. The graphs from this family are divisible design and integral.     

Algebraic Cayley graphs over finite fields

A new algebraic Cayley graph is constructed using finite fields. It provides a more flexible source of expander graphs. Its connectedness, the number of connected components, and diameter bound are studied via Weil's estimate for character sums. Furthermore, we study the algorithmic problem of computing the number of connected components and establish a link to the integer factorization problem.     

On the girth of random Cayley graphs

We prove that random d‐regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (log_d‐1|G|)^1/2/2 and that random d‐regular Cayley graphs of simple algebraic groups over ??_q asymptotically almost surely have girth at least log _d‐1|G|/dim(G). For the symmetric p‐groups the girth is between loglog |G| and (log |G|)^α with α < 1. Several conjectures and open questions are presented. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

The thresholds for diameter 2 in random Cayley graphs

Given a group G, the model denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any and any family of groups G_k of order n_k for which , a graph with high probability has diameter at most 2 if and with high probability has diameter greater than 2 if . We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erd?s‐Renyi random graphs. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 218–235, 2014     

Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph $G$, denoted ${\chi }_D\left(G\right)$, is defined as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism of $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma$ defined over certain abelian groups $A$ with $\left|A\right|=n$, and show that with probability at least $1?n^{?\Omega (logn)}$, ${\chi }_D\left(\Gamma \right)\le \chi \left(\Gamma \right)+1$.     

Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales

The Alon–Roichman theorem states that for every ε> 0 there is a constant c(ε), such that the Cayley graph of a finite group G with respect to c(ε)log ∣G∣ elements of G, chosen independently and uniformly at random, has expected second largest eigenvalue less than ε. In particular, such a graph is an expander with high probability. Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a new proof of the result, improving the bounds even further. When considered for a general group G, our bounds are in a sense best possible. We also give a generalization of the Alon–Roichman theorem to random coset graphs. Our proof uses a Hoeffding‐type result for operator valued random variables, which we believe can be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Further results on the enumeration of hamilton paths in Cayley digraphs on semidirect products of cyclic groups

First, let m and n be positive integers such that n is odd and gcd(m,n)=1. Let G be the semidirect product of cyclic groups given by . Then the number of hamilton paths in Cay(G:x,y) (with initial vertex 1) is one fewer than the number of visible lattice points that lie on the closed quadrilateral whose vertices in consecutive order are (0,0), (4mn²+2n,16m²n), (n,4m), and (0,8m). Second, let m and n be positive integers such that n is odd. Let G be the semidirect product of cyclic groups given by . Then the number of hamilton paths in Cay(G:x,y) (with initial vertex 1) is (3m-1)n+m⌊(n+1)/3⌋+1.     

Finite locally primitive abelian Cayley graphs

Let Γ be a finite connected locally primitive Cayley graph of an abelian group.It is shown that one of the following holds:(1) Γ = Kn,Kn,n,Kn,n-nK2,Kn × · · · × Kn;(2) Γ is the standard double cover of Kn × · · · × Kn ;(3) Γ is a normal or a bi-normal Cayley graph of an elementary abelian or a meta-abelian 2-group.     

Algebraic Cayley graphs over finite local rings

In this work, we define and study the algebraic Cayley directed graph over a finite local ring. Its vertex set is the unit group of a finite extension of a finite local ring R and its adjacency condition is that the quotient is a monic primary polynomial. We investigate its connectedness and diameter bound, and we also show that our graph is an expander graph. In addition, if a local ring has nilpotency two, then we obtain a better view of our graph from the lifting of the graph over its residue field.     

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 large family of cospectral Cayley graphs over dicyclic groups

For a finite group G and an inverse closed subset $S\subseteq G\setminus \{e\}$, the Cayley graph $X(G,S)$ has vertex set G and two vertices $x,y\in G$ are adjacent if and only if $x{y}^{-1}\in S$. Two graphs are called cospectral if their adjacency matrices have the same spectrum. Let $p\ge 3$ be a prime number and $T_{4p}$ be the dicyclic group of order 4p. In this paper, with the help of the characters from representation theory, we construct a large family of pairwise non-isomorphic and cospectral Cayley graphs over the dicyclic group $T_{4p}$ with $p\ge 23$, and find several pairs of non-isomorphic and cospectral Cayley graphs for $5\le p\le 19$.     

An infinite family of cubic nonnormal Cayley graphs on nonabelian simple groups

We construct a connected cubic nonnormal Cayley graph on ${\mathrm{A}}_{2^m?1}$ for each integer $m?4$ and determine its full automorphism group. This is the first infinite family of connected cubic nonnormal Cayley graphs on nonabelian simple groups.     

Normal and non-normal Cayley graphs for symmetric groups

A Cayley graph is said to be an NNN-graph if its automorphism group contains two isomorphic regular subgroups where one is normal and the other is non-normal. In this paper, we show that there exist NNN-graphs among the Cayley graphs for symmetric groups $S_n$ if and only if $n?5$.     

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.