Closed walks and eigenvalues of Abelian Cayley graphs

We show that Abelian Cayley graphs contain many closed walks of even length. This implies that given $k?3$, for each $\mathrm{?}>0$, there exists $C=C(\mathrm{?},k)>0$ such that for each Abelian group G and each symmetric subset S of G with $1?S$, the number of eigenvalues ${\lambda }_i$ of the Cayley graph $X=X(G,S)$ such that ${\lambda }_i?k?\mathrm{?}$ is at least $C?|G|$. This can be regarded as an analogue for Abelian Cayley graphs of a theorem of Serre for regular graphs. To cite this article: S.M. Cioab?, C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Cayley digraphs and graphs

We shortly recall some definitions that involve refinements of connectivity, and a theorem of Y.O. Hamidoune. We consider some aspects of Cayley digraphs and vertex- and arc-transitive digraphs that he investigated.     

Embedding graphs in Cayley graphs

IfY is a finite graph then it is known that every sufficiently large groupG has a Cayley graph containing an induced subgraph isomorphic toY. This raises the question as to what is sufficiently large. Babai and Sós have used a probabilistic argument to show that |G| > 9.5 |Y|³ suffices. Using a form of greedy algorithm we strengthen this to (2 + \sqrt 3 )|Y|^3 $$ " align="middle" border="0"> . Some related results on finite and infinite groups are included.     

Finite edge-transitive Cayley graphs and rotary Cayley maps

This paper aims to develop a theory for studying Cayley graphs, especially for those with a high degree of symmetry. The theory consists of analysing several types of basic Cayley graphs (normal, bi-normal, and core-free), and analysing several operations of Cayley graphs (core quotient, normal quotient, and imprimitive quotient). It provides methods for constructing and characterising various combinatorial objects, such as half-transitive graphs, (orientable and non-orientable) regular Cayley maps, vertex-transitive non-Cayley graphs, and permutation groups containing certain regular subgroups.

In particular, a characterisation is given of locally primitive holomorph Cayley graphs, and a classification is given of rotary Cayley maps of simple groups. Also a complete classification is given of primitive permutation groups that contain a regular dihedral subgroup.

     

Balanced Cayley graphs and balanced planar graphs

A balanced graph is a bipartite graph with no induced circuit of length . These graphs arise in integer linear programming. We focus on graph-algebraic properties of balanced graphs to prove a complete classification of balanced Cayley graphs on abelian groups. Moreover, in this paper, we prove that there is no cubic balanced planar graph. Finally, some remarkable conjectures for balanced regular graphs are also presented. The graphs in this paper are simple.     

Spectra of Cayley graphs

By a result of L. Lovász, the determination of the spectrum of any graph with transitive automorphism group easily reduces to that of some Cayley graph.We derive an expression for the spectrum of the Cayley graph X(G,H) in terms of irreducible characters of the group G:

for any natural number t, where ξ_i is an irreducible character (over $\text{C}$), of degree n_i , and λ_i,1 ,…, λ_i,ni are eigenvalues of X(G, H), each one n_i times. (σn_i² = n = | G | is the total'number of eigenvalues.) Using this formula for t = 1,…, n_i one can obtain a polynomial of degree n_i whose roots are λ_i,1,…,λ_i,ni. The results are formulated for directed graphs with colored edges. We apply the results to dihedral groups and prove the existence of k nonisomorphic Cayley graphs of D_p with the same spectrum provided p > 64k, prime.     

Automorphisms of Cayley graphs

The aim of this paper is to characterize subgroups of non-regular automorphism groups of Cayley graphs. Relations between group automorphisms, graph automorphisms and permutations of the edge set of Cayley graphs are investigated.     

Random Cayley graphs and expanders

For every 1 > δ > 0 there exists a c = c(δ) > 0 such that for every group G of order n, and for a set S of c(δ) log n random elements in the group, the expected value of the second largest eigenvalue of the normalized adjacency matrix of the Cayley graph X(G, S) is at most (1 - δ). This implies that almost every such a graph is an ?(δ)-expander. For Abelian groups this is essentially tight, and explicit constructions can be given in some cases. © 1994 John Wiley & Sons, Inc.     

Shifts in Cayley graphs

An automorphism of an undirected simple graph is called a shift if it maps every vertex to an adjacent one. For all finite groups G, we determine the minimum nonzero valency of a Cayley graph on G that does not admit a shift. We also get a classification of groups with all involutions central and such that for every pair a,b of elements of the group, one of ab=ba, aba⁻¹=b⁻¹, bab⁻¹=a⁻¹ or a²=b^±2 holds.     

Cayley graphs and automatic sequences

We study those automatic sequences which are produced by an automaton whose underlying graph is the Cayley graph of a finite group. For 2-automatic sequences, we find a characterization in terms of what we call homogeneity, and among homogeneous sequences, we single out those enjoying what we call self-similarity. It turns out that 2-self-similar sequences (viewed up to a permutation of their alphabet) are in bijection with many interesting objects, for example dessins d’enfants (covers of the Riemann sphere with three points removed). For any p, we show that, in the case of an automatic sequence produced “by a Cayley graph,” the group and indeed the automaton can be recovered canonically from the sequence. Further, we show that a rational fraction may be associated with any automatic sequence. To compute this fraction explicitly, knowledge of a certain graph is required. We prove that for the sequences studied in the first part, the graph is simply the Cayley graph that we start from, and so calculations are possible. We give applications to the study of the frequencies of letters.     

Hash functions and Cayley graphs

We introduce cryptographic hash functions that are in correspondence with directed Cayley graphs, and for which finding collisions is essentially equivalent to finding short factorisations in groups. We show why having a large girth and a small diameter are properties that are relevant to hashing, and illustrate those ideas by proposing actual easily computable hash functions that meet those requirements.     

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.     

Self-dual embeddings of Cayley graphs

A method for constructing both orientable and non-orientable embeddings of Cayley graphs is described. This method yields all the previously known constructions in addition to producing some new self-dual embeddings.     

Hamiltonian circuits in Cayley graphs

The following result is proved: If either G is a finite abelian group or a semidirect product of a cyclic group of prime order by a finite abelian group of odd order, then every connected Cayley graph of G is hamiltonian.     

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.     

Discrepancy of random graphs and hypergraphs

Answering in a strong form a question posed by Bollobás and Scott, in this paper we determine the discrepancy between two random k‐uniform hypergraphs, up to a constant factor depending solely on k. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 47, 147–162, 2015     

Cayley graphs with few automorphisms

Journal of Algebraic Combinatorics - We show that every finitely generated group G with an element of order at least $$bigl (5{{,mathrm{rank},}}(G)bigr )^{12}$$ admits a locally finite...