# Questions tagged [cayley-graphs]

Questions concerning Cayley graphs, regardless of whether the group be finite, infinite, abelian, non-abelian. Strong connections to geometric group theory.

52
questions

5
votes

0
answers

153
views

### Groups of non-orientable genus 1 and 2

The non-orientable genus (aka crosscap-number) $\overline{\gamma}(G)$ of a finite group $G$ is the minimum non-orientable genus among all its connected Cayley graphs (and $0$ if $G$ has a planar ...

2
votes

0
answers

105
views

### Chromatic numbers of Cayley graphs induced by Hamming balls

The motivation for this question is to find, for a fixed odd $p$ and large $n$, sets $A\subset (\mathbb Z/p\mathbb Z)^n$ with $|A|> cp^n$ for some fixed $c$, where the difference set $A-A:=\{a-a': ...

2
votes

0
answers

78
views

### Bruhat-Tits tree as Cayley graph of free group

$\DeclareMathOperator\BT{BT}\DeclareMathOperator\GL{GL}$Let $p > 2$ be a prime and $n = \frac{p + 1}{2}$. We can identify the vertices of Bruhat-Tits tree $\BT(\mathbb Q_p)$ with the elements in ...

3
votes

0
answers

56
views

### Hamiltonian cycles in Cayley graph on alternating group

Let $G=\operatorname{Cay}(A_n,S)$ be the Cayley graph on the Alternating group $A_n\quad n\ge4$ with generating set $S=\{(1,2,3),(1,2,4),\ldots,(1,4,2),(1,3,2)\}$. One Hamiltonian cycle in $G$ for $n=...

3
votes

0
answers

307
views

### What about a Cayley n-complex for n>2?

Let $G$ be a finitely presented group. The Cayley graph of the finite generating set is a $1$-complex where the $0$-cells are the elements of $G$ and the $1$-cells are given by the generators (...

3
votes

1
answer

185
views

### Explicit formula for embedding Cayley graph of free group into hyperbolic space

The problem is to embed Cayley graph of free group with $n\geq2$ generators (the same as Bethe lattice with coordination number $2n$) into any model of $\mathbb{H}^2$ (we have no model preference, the ...

4
votes

0
answers

102
views

### When is a Schreier coset graph vertex transitive

When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive?
It is well known that when $H$ is normal, the Schreier coset graph ...

1
vote

2
answers

106
views

### Difference in chromatic number between Schreier coset graphs and Cayley graphs

Can the Schreier coset graphs can be seen as a subgraph of Cayley graph on the same groups(neglecting the loop edges) and, hence, have their chromatic numbers bounded by the chromatic numbers of the ...

2
votes

1
answer

84
views

### Imposing reciprocity in the definition of vertex-transitivity

A simple, undirected graph is vertex-transitive if for any pair of vertices $x,y$, there exists an automorphism (adjacency-preserving self-bijection) $\phi$ such that $\phi(x)=y$.
What if, instead of ...

0
votes

1
answer

101
views

### Bound on chromatic number of graphs on any finite $p$-group

Is the chromatic number of a Cayley graph on $p$-groups with any generating set bounded by the chromatic number of the maximal induced circulant subgraph?
I think yes. Because for one, the main ...

0
votes

1
answer

71
views

### Extending the vertex coloring of circulant graph to graph on $p$-group

Let $G_1$ be a circulant graph of prime order $p$. This implies that $G_1$ is the Cayley graph on $\mathbb{Z}_p$ with some generating set $S_1$. I am interested in knowing the characterizations of the ...

0
votes

0
answers

79
views

### Does the following hermitian matrix represent the adjacency matrix of the Rubik's cube?

The Rubik's cube can be generated with quarter-turn clockwise/counterclockwise twists of each of the front, back, left, right, up, and down faces:
$$\langle F_1,B_1,L_1,R_1,U_1,D_1,F_3,B_3,L_3,R_3,U_3,...

1
vote

0
answers

44
views

### Circulant graphs chromatically dominated by powers of cycles

Suppose we can color the vertices of powers of cycles $C_n^k$ using $c$ colors such that each of the color classes $c_i$ have $v_i$ number of vertices. Can we always color the circulant of degree $2k$ ...

1
vote

0
answers

106
views

### halved and folded hypercube duality

Notation. Consider the group $\Gamma=\mathbb{Z}_2^n$. I will denote the group operation aditively and by $\epsilon_i=(0,\dots,0,1,0,\dots,0)$ I denote the canonical generators. Let's define also $\...

6
votes

1
answer

229
views

### Is the function $k(g,h) = \frac{1}{1+\lvert gh^{-1}\rvert}$ positive definite?

Let $G$ be a finite group, $S \subset G$ a generating set, closed under taking inverses, and $\lvert\cdot\rvert$ the word length with respect to this set $S$.
Question. Is the function $k(g,h) = \...

12
votes

1
answer

525
views

### Is the Petersen graph a "Cayley graph" of some more general group-like structure?

The Petersen graph is the smallest vertex-transitive graph which is not a Cayley graph. Is it the "Cayley graph" of some slightly more general group-like structure?

1
vote

0
answers

77
views

### Example of family of Cayley graphs with Ramanujan behaviour on finite $p$-groups

This is a very general question: are there known examples of Ramanujan behaviour of Cayley graphs obtained from family of finite p-groups?
${\mathrm{\bf Adjacency~matrix:}}$ Given a graph ${\mathcal{G}...

0
votes

0
answers

106
views

### Procedure to color the edges of a circulant graph

From the first theorem in this paper, it is clear that a cayley graph on abelian group for all generating sets of even order is class $1$, that is can be edge colored in exactly $\Delta$ colors. But, ...

3
votes

0
answers

62
views

### how do I find eigenvalues of Cayley graph for one subset given a different subset

How do I find eigenvalues for the adjacency matrix of Cayley graph $X(S_n,S)$ where $S_n$ is the symmetric group of order $n$ and $S$ is the set of transpositions $(i,i+1)$, if the eigenvalues of the ...

-1
votes

1
answer

148
views

### Which line graphs of Cayley graphs are Cayley

When are the line graphs of Cayley graphs Cayley?
From this link we can know when the line graphs of complete graphs are cayley. But, my question pertains to the larger class of Cayley graphs. Are ...

1
vote

1
answer

137
views

### Cayley graphs on $Z_{11}$ and $Z_p$

I want to find all cayley graphs on $Z_{11}$. I know how many connected cayley graphs exist but i want to find all of them, connected or not, to find their eigenvalues. I found some of them and a ...

2
votes

0
answers

46
views

### Path-covering for vertex-transitive graphs

I have the following dummy problem:
Claim - There exists $N$ such that for $n > N$, if $G_n$ be a connected directed vertex-transitive graph with $n$ vertices, then there exists a set $S$ of paths ...

0
votes

1
answer

137
views

### Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques

Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...

1
vote

1
answer

187
views

### Cayley graphs do not have isolated maximal cliques

Let a Cayley graph $G$ of a group $H$ with respect to the generating set $\{s_i\}$ have a clique of order $> 2$. In addition assume the graph $G$ is non-complete. If the clique size is less than ...

4
votes

2
answers

372
views

### Transposition Cayley graphs are planar

Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13)...

0
votes

1
answer

93
views

### Recognizing perfect Cayley graphs as tensor products

It is known (and can easily be seen) that a unitary Cayley graph on $n=\prod_ip_i$, ($p_i$ distinct primes) vertices with $n$ square-free can be recognized as the tensor product of the graphs $K_{p_i}$...

4
votes

1
answer

260
views

### $C_4\times C_2 : C_2$: what does this mean?

I am reading this paper where the object $C_4\times C_2 : C_2$ is used as a group structure. I know that $C_n$ is a cyclic group but don't know what kind of operation between groups is identified by ...

1
vote

0
answers

108
views

### Chromatic number of certain graphs with high maximum degree

Let $G$ be the graph of even order $n$ and size $\ge\frac{n^2}{4}$ which is a Cayley graph on a nilpotent group but not complete. Can the chromatic number of this graph be determined in polynomial ...

4
votes

1
answer

215
views

### Diameter of Cayley graphs of finite simple groups

Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...

0
votes

1
answer

255
views

### A vertex transitive graph has a near perfect/ matching missing an independent set of vertices

Consider a power of cycle graph $C_n^k\,\,,\frac{n}{2}>k\ge2$, represented as a Cayley graph with generating set $\{1,2,\ldots, k,n-k,\ldots,n-1\}$ on the Group $\mathbb{Z}_n$. Supposing I remove ...

6
votes

1
answer

215
views

### Vanishing of certain coefficients coming from Coxeter groups

Let $\left(W\text{, }S\right)$ be a Coxeter system. For every $w\in W$ let us write $\left|w\right|$ for the length of $w$. Set $\lambda\left(e\right)=1$ where $e\in W$ denotes the neutral element of ...

1
vote

0
answers

138
views

### Are all even regular undirected Cayley graphs of Class 1?

Are even order Cayley graphs of Class 1, that is, can they be edge-colored with exactly $m$ colors, where $m$ is the degree of each vertex?
I think yes, because of the symmetry the Cayley graphs ...

4
votes

1
answer

133
views

### Diameter for permutations of bounded support

Let $S\subset \textrm{Sym}(n)$ be a set of permutations each of which is of bounded support, that is, each $\sigma\in S$ moves $O(1)$ elements of $\{1,2,\dotsc,n\}$. Let $\Gamma$ be the graph whose ...

3
votes

0
answers

198
views

### Growth functions of finite group - computation, typical behaviour, surveys?

Looking on the growth function for Rubik's group and symmetric group, one sees rather different behaviour:
Rubik's growth in LOG scale (see MO322877):
S_n n=9 growth and nice fit by normal ...

4
votes

1
answer

194
views

### Total coloring conjecture for Cayley graphs

The total coloring conjecture (TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...

4
votes

1
answer

143
views

### Cliques in Cayley graph on $n$-cycles

Let $S\subset S_n$ be the set of all $n$-cycles. I want to know if the Cayley graph $(S_n,S)$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $1-o(1)$ dense subgraphs....

5
votes

1
answer

333
views

### Cayley graph properties

Consider an infinite graph that satisfies the following property: if any finite set of vertices is removed (and all the adjacent edges), then the resulting graph has only one infinite connected ...

15
votes

1
answer

445
views

### Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...

2
votes

2
answers

186
views

### Distance regular Cayley graphs on $Z_2^n$?

Let $Z_2^n$ be group $Z_2 \times Z_2 \times \cdots \times Z_2$ with operation Exclusive-or. I'd like to know if the $Cay(Z_2^n,S)$ for $S \subset Z_2^n \setminus \{0\}$ is distance regular graph or ...

20
votes

4
answers

1k
views

### Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$

The Cayley graph of $A_5$ with two generators of order 5 seems rather complicated. What is its graph genus (orientable or non-orientable)?
The best I could get by trial and error is an embedding ...

0
votes

2
answers

123
views

### coloring infinite vertex transitive graph without large cliques

Let $G$ be an infinite vertex-transitive graph (this means that for every $u,w \in V(G)$ there exists an automorphism $\tau$ of $G$ such that $\tau(u) = v$).
We assume that $G$ is undirected, and does ...

5
votes

1
answer

135
views

### Inertia of a class of Cayley graphs

Let $H^n_2(d)$ be the Cayley graph with vertex set $\{0,1\}^n$ where two strings form an edge iff they have Hamming distance at least $d$. What is the inertia of these graphs, that is, the numbers of ...

5
votes

2
answers

624
views

### A generously vertex transitive graph which is not Cayley?

A graph is vertex transitive if $x \mapsto y$ by an automorphism.
A graph is generously vertex transitive if $x \mapsto y \mapsto x$ by an automorphism.
Simple facts:
GVT $\rightarrow$ unimodular. ...

15
votes

0
answers

225
views

### Approximation of the effective resistance on Cayley graph

Let $\Gamma$ be a finitely generated group, and denote by $G$ the Cayley graph of $\Gamma$. Denote by $d_R$ the resistance distance metric on this graph. The resistance distance metric between the ...

3
votes

0
answers

280
views

### Induced graphs of Cayley graph

I have a Cayley graph $\mathrm{Cay}(G,S)$, its group presentation $G=\langle S | R \rangle$, and it becomes a metric graph by assigning a length equal to $1$ to each edge. I also have an induced ...

19
votes

3
answers

2k
views

### Infinitely many finitely generated groups having the same Cayley graph

Is there an unlabeled locally-finite graph which is a Cayley graph of an infinitely many non-isomorphic groups with respect to suitably chosen generating sets?

5
votes

0
answers

267
views

### Complexity of property of being vertex-transitive resp. of being a Cayley graph

Suppose I gave you a finite graph, and asked you whether it was vertex-transitive. How hard is that algorithmically?
The second question is: suppose I gave you a vertex transitive finite graph, and ...

11
votes

4
answers

1k
views

### Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley graph of any abelian group?

It's the first question I post here :) I'm sorry if the question is too specific or if it's somehow repeating others.
In other words, my question is the following. Consider a Cayley graph $\Gamma$ of ...

26
votes

4
answers

1k
views

### What relationship, if any, is there between the diameter of the Cayley graph and the average distance between group elements?

It's known that every position of Rubik's cube can be solved in 20 moves or less. That page includes a nice table of the number of positions of Rubik's cube which can be solved in k moves, for $k = 0,...

8
votes

2
answers

2k
views

### Quasi-isometries vs Cayley Graphs

The following questions might be trivial, however, I couldn't solve them:
Let $G$ be generated by a finite symmetric set $S$. Suppose that $\Gamma(G,S)$ is the corresponding right Cayley graph of $G$...