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

182 questions
Filter by
Sorted by
Tagged with
26 views

### Converse for Cayley digraphs

"It can be shown that, conversely,..... for some group."- can you clearly show or provide good references for proof of the converse? Also, I would appreciate more of an explanation for ...
1 vote
59 views

### Checking for indepenedent sets in a bipartite graph with equal number of odd and even elements in SageMath

By using the IndependentSets module in SageMath, we can list all the independent sets of a graph. Suppose I have a bipartite graph on the Symmetric Group with partite sets consisting of even and odd ...
51 views

### Constructing Cayley Graphs in SageMath

I am having confusions in constructing a Cayley Graph in Sage Math. Say, I want to construct the Cayley graph on the Symmetric Group $S_4$ with respect to the generating set consisting of all ...
121 views

### Are jumps in the growth function of an infinite group increasing?

Let $G$ be a group with a $S$ a finite subset of $G$ generating it, with $\{e\}\in S$ and $S=S^{-1}$, and let $\gamma_G^S$ be the growth function of $G$ respect to $S$, that is, $\gamma_G^S(l)$ is the ...
71 views

### The number of closed paths in the square lattice $\mathbb{Z}^2$ with length $n$ and starting and ending points at $(0,0)$.

I'm thinking about this problem right now. Problem:Consider a lattice point consisting of $\mathbb{Z}^2$ points. If $n$ is even, i.e., $n=2p$, then Show that the number of closed paths in the square ...
1 vote
64 views

1 vote
59 views

### Cayley graph with opposite action: is the group abelian?

Let $G$ be a group, let $S$ be a set of generators and let $\Gamma=\Gamma(G,S)$ be the Cayley graph, where there is an edge between $g$ and $h$ if and only if $h=gs$ for some $s\in S$. We know that ...
114 views

58 views

### rate of escape free group with 2 generators

I want to find rate of escape (drift) on free group (with d generators). From here (page 2): https://arxiv.org/pdf/math/0506129.pdf I know the answer = 1 But I can't fully figure out why I know there ...
25 views

### Will a path in Cayley graphs end at unique vertices when started at distinct vertices and traversed along same edges

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

### Different metrics on Cayley graphs

On every (say undirected, for simplicity) Cayley graph $\Gamma(G, S)$ we have the word ("geodesic") metric, that is $d_w(g, h)$ is the minimum of lenghts of paths joining $g$ to $h$. This ...
98 views

### Cayley graphs of product of groups

From this question, we have that the Cayley graph of direct product of two groups is a cartesian product of some cayley graphs on the factor groups. But, I do not see this translation easily. ...
63 views

### Does the group growth rate limit the number of edges going out of a vertex in its Cayley graph?

The growth rate of a group $B_n(G, T)$ is based on the number of vertices that can be reached from a given one by $n$ steps along an edge in the Cayley graph of the group, where $G$ is the group (or ...
113 views

147 views

116 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 ...
35 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 ...
35 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 ...
42 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 ...
1 vote
34 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 ...
86 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 ...
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 ...