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

29 questions
Filter by
Sorted by
Tagged with
30 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$. ...
130 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 ...
263 views

211 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 ...
91 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 ...
179 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$ ...
84 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 ...
204 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 ...
124 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 ...
123 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 ...
161 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 ...
118 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 ...
111 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....
299 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 ...
359 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 ...
137 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 ...
833 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 ...
111 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 ...
118 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 ...
512 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. ...
200 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 ...
271 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 ...
250 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 ...
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 ...