# Questions tagged [cayley-graphs]

Cayley graphs are graphs obtained from a group $G$ in a such way that vertices are elements of the group and edges are added using some generating set $S\subseteq G$.

149 questions
Filter by
Sorted by
Tagged with
31 views

### Groups with two ends: showing that either $E\Delta gE$ is finite or $(E\Delta gE)^\complement$ is finite.

Let $G$ be a finitely generated group with $e(G) = 2$, and let $\Gamma$ be a Cayley graph of $G$. There is then a finite subgraph $C$ such that $\Gamma \setminus C$ has exactly two connected, ...
64 views

### Geometric Group Theory, Meier lemma 11.30 about a two-ended groups $G$

This is probably a basic algebraic (or even set-theoretic) matter. I am reading "Groups, Graphs and Trees" by J. Meier. It's about Lemma 11.30 which is left as an exercise to the reader. ...
99 views

### Seeking a combinatorial proof of $2n^{n-3} = \sum_{m=1}^{n-1}\binom{n-2}{m-1}m^{m-2}(n-m)^{n-m-2}$

I need to prove the following using Combinatorial proof: (Not using math laws But finding two similar Combinatorial problems) $$2n^{n-3} = \sum_{m=1}^{n-1}\binom{n-2}{m-1}m^{m-2}(n-m)^{n-m-2}$$ (...
43 views

### Cayley Graph and Cayley Digraph

I am trying to understand the definition of a Cayley graph of a group $G$: Is Cayley graph and Cayley Digraph the same thing? If Cayley graph and digraph have the same meaning, then can we define an ...
22 views

### Can a Hamiltonian cycle of an undirected Cayley graph contain inverses of the generating elements?

Let $G$ be a finite group and $S$ be a subset of $G$. Let us define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed. Definition: The ...
31 views

### Does a longest cycle contain maximum number of each generating element

Let $G$ be a finite group and $S$ be a subset of $G$. We define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed. Definition: The Cayley ...
15 views

### What can be said about the stationary distribution of the Latch Cube?

Katsuhiko Okamoto's Latch Cube is similar to the standard $3\times 3$ Rubik's cube with the added features that on one of the faces of each of the edge cubies, there is an arrow identifying a ...
26 views

### The longest cycle and relation between the generating elements of a Cayley graph

Let $G$ be a finite group and $S$ be a subset of $G$. We define the Cayley graph of $G$ with respect to $S$ as follows, provided that $1 {\not\in} S$ and $S$ is inverse closed. Definition: The Cayley ...
31 views

### Difference between the Cayley Graph and the Cayley Sum Graph.

Could someone help me visualize the difference between the following graphs? Take $G$ to be a group generated by the symmetric generating set $S$. Take $g, h$ to be elements of $G$. We define the ...
26 views

### Representing relationships shown by cycles in Cayley graphs using congruence relations and solving them

Consider a finite group $G=\mathbb{Z}_3 \times \mathbb{Z}_5$. Let the undirected Cayley graph of the group be gererated by $\{s,s^{-1}, t, t^{-1}\}$, where $|s|=3, |t|=5$. Then different cycles in the ...
12 views

71 views

37 views

### Paths, Cycles, Free Groups, and Trees

First some definitions (which come from Geometric Group Theory by Clara Loh) Let $X=(V,E)$ be a graph. Let $n \in \Bbb{N} \cup \{\infty \}$. A path in $X$ of length $n$ is a sequence $v_0,....,v_n$ ...
84 views

### eigenvalues of a direct sum of matrices

According to Bacher's article, the eigenvalues of the adjacency matrix of Cayley graph of the symmetric group of order $n$ are $2-2\cos(\pi/n)$; my question is: If we know that this adjacency matrix ...
25 views

### Given a subgroup $H \leq G$ of infinite index, there is a path in the Cayley graph of $G$ always moving “away” from $H$?

If we have a group $G$ and $H \leq G$ with infinite index, show there is an infinite sequence of vertices $(a_i)_{i \in \mathbb{N}}$ in the Cayley graph $\Gamma$ of $G$ (with respect to some not ...
70 views

### Connected and bridgeless properties of Cayley graphs (or vertex transitive graphs)

a) How can we prove that a Cayley graph (or a vertex transitive graph) is connected and bridgeless? b) It is known that a even ordered Cayley graph (or vertex transitive graph) has a perfect matching ...
61 views

### Deducing information about a group from its Cayley graph.

Let be a Cayley graph of group $G$ ( $e$ is the neutral element ). Is the group commutative? How do I see that from the graph ? I am not sure if my thinking is correct, the red arrows mean ...
239 views

### How to see if a subgroup is normal from Cayley graph

Let be a Cayley diagram of group $G$. Let $H$ be the orbit of element p. Is $H$ a normal subgroup of $G$? Is there a simple way to check that because going by definition seems complicated. I tried ...
23 views

### Uncorrelatedness for random elements of finitely generated groups?

Suppose $G$ is a finitely generated group, $A$ is its finite set of generators. Lets denote the metric induced by the Cayley graph $Cay(G, A)$ on $G$ as $d$. Suppose $\{X_i\}_{n = 0}^\infty$ is a ...
53 views

### If we add more relations to a presentation will it always form a quotient group?

Specifically, if I have a presentation $\left<G|R\right>$, and I look at the presentation $\left<G|R,R_1\right>$ is always true that \left<G|R,R_1\right>\cong\left<G|R\right>...
65 views

### Eigenspaces of the Cayley Graph Cay$(S_n,T_n)$ on adjacent transpositions

Consider the Cayley graph G = Cay$(S_n,T_n)$ where $S_n$ is the symmetric group and $T_n = \{(i,i+1) | 1 \leq i \leq n-1\}$ is the set of adjacent transpositions. G is sometimes called the ...
97 views

### Cayley digraphs of a group

I could not find an answer to the questions online. How many loopless Cayley digraphs of a group G there are? How many loopless Cayley graphs of a group G there are if |G| = n and G has i self-...
56 views

### Generating words in a finitely presented group in SAGE

I'm trying to get a list of all words of length $n$ (in the word metric sense) in some finitely presented group. I have tried some very naive enumerations but it is very slow. Is there an efficient ...
70 views

### Automorphisms, order and degree uniquely determine a regular graph

Does Automorphism group combined with the order and degree uniquely determine any regular graph? What about any (non-regular) graph? I think yes, because the automorphism contain within them the ...
84 views

### With reference to the Lifting of Hamiltonian cycles

Can someone please help to understand about the concept of "lifting Hamiltonian cycles (in Cayley graphs)"? As an example how the existence of a Hamiltonian cycle is shown by using the concept of ...
86 views

### Find the subgroup of $\mathbb{Z}_{12}$ generated by the subset $\{4,6\}$. Also draw the digraph of this subgroup $\langle\{4,6\} \rangle$.

I have the following problem: Find the subgroup of $\mathbb{Z}_{12}$ generated by the subset $\{4,6\}$. Also draw the digraph of this subgroup $\langle\{4,6\} \rangle$. I've done the first part ...
78 views

### Are Cayley Graphs weakly or strongly connected?

I'm working my way through Meier's Groups, Graphs and Trees and I'm confused by the proof he gives for one of Cayley's Theorems, namely Every finitely generated group can be represented as a ...
Let $G$ be a group and $S \subseteq G$ be a generating set of $G$. The Cayley digraph of $G$ with respect to $S$, $X=\overrightarrow {\operatorname{Cay}}(G, S)$ is a graph whose vertices are the ...