# 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.

**2**

votes

**0**answers

52 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 ...

**3**

votes

**1**answer

81 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

232 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

279 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 ...

**3**

votes

**2**answers

109 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 ...

**12**

votes

**1**answer

275 views

### Genus of Cayley graph of $A_5$ with two generators of order 5

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

**0**

votes

**2**answers

99 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

109 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 ...

**12**

votes

**0**answers

175 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

260 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 ...

**5**

votes

**0**answers

233 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

933 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 ...

**7**

votes

**2**answers

1k 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$...

**64**

votes

**6**answers

6k views

### Which graphs are Cayley graphs?

Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main ...