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

57 questions
Filter by
Sorted by
Tagged with
94 views

### Edge coloring of a graph on alternating groups

Let $G$ be the Cayley graph on the alternating group $A_n\,n\ge4$ with generating set S=\begin{cases}\{(1,2,3),(1,3,2),\\(1,2,\ldots,n),(1,n,n-1,\ldots,2)\}, &n\ \text{odd}\\ \{(1,2,3),(1,3,2),\\...
296 views

### Does every infinite, connected, locally finite, vertex-transitive graph have a leafless spanning tree?

My question is Let $G$ be an infinite, connected, locally finite, vertex-transitive graph. Must $G$ have the following substructures? i) a leafless spanning tree; ii) a spanning forest consisting ...
142 views

### (How) does the spectral gap of the $n\times n$ Rubik's cube close with $n$?

Consider the spectrum of the adjacency matrix $A$ of the Cayley graph of the standard, 3x3x3 Rubik's cube generated with the usual quarter-turn and half-turn twists of each face (the Singmaster ...
128 views

### Does the visual boundary of any one-ended Cayley graph contain at least three points?

Let $\Gamma$ be a Cayley graph of a finitely generated group. We can define the visual boundary of $\Gamma$ with respect to some base vertex $b$, denoted $\partial \Gamma$, as the set of geodesic rays ...
168 views

### Property $(T)$ for $\mathrm{SL}_2(\mathbb{Z}) \ltimes \mathbb{Z}^2$

(This is in part a request for references and in part a somewhat pedagogical question.) I gave a course on expanders seven years ago, and I am giving a course on expanders again now. We will soon do ...
125 views

### Bandwidth of finite groups

For a generating set $S$ of a group $G$ denote by $\mathrm{Cay}(G,S)$ the corresponding Cayley graph. For a finite graph $A$ denote by $\beta(A)$ its bandwidth. Question: Has the "group bandwidth&...
187 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 ...
129 views

336 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 (...
249 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 ...
139 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
120 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 ...
90 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 ...
109 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 ...
76 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 ...
1 vote
46 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
115 views

691 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
83 views

105 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}$...
299 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
109 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 ...
245 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$ ...
328 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 ...
221 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
149 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 ...
141 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 ...
206 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 ...
215 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 ...
158 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....
354 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 ...
495 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 ...
227 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 ...
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 ...
133 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 ...
138 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 ...
734 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. ...
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 ...
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 ...