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

Filter by
Sorted by
Tagged with
1
vote
2answers
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, ...
2
votes
0answers
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. ...
2
votes
1answer
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}$$ (...
0
votes
2answers
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 ...
2
votes
1answer
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 ...
3
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
12 views

Finding the relationship between generating elements represented by a Hamiltonian cycle of a Cayley graph

Consider an undirected Cayley graph of a finite group $\mathbb{Z}_p \times \mathbb{Z}_q$, where $p$ and $q$ are distinct primes. Let the generating set for the Cayley graph be $S=\{g_p, g_q\}$, where $...
0
votes
0answers
22 views

Relationship between the generating elements given by the Hamiltonian cycle of a Cayley graph

Consider the Cayley graph of $\mathbb{Z}_3 \times \mathbb{Z}_5$ generated by the generating set $S=\{g_1=(1,0), g_2=(0,1)\}$. Then $|g_1|=3, |g_2|=5$. Consider a Hamiltonian cycle, $ABCDEFGHIKJLMNO$. ...
1
vote
0answers
25 views

Multiplicity of eigenvalues of adjacency operator and dimension of represenations

Let $G$ be a finite group, $S\subset G$ a symmetric subset of generators of $G$ (symmetric means $S=S^{-1}$), and $Cay(G,S)$ the corresponding Cayley graph. I'm trying to show that if the minimal ...
0
votes
0answers
30 views

Relationship between generating elements of Cayley graphs

When we consider any cycle in a Cayley graph, it represents a relationship between the generating elements of the graph. As an example, for a Cayley graph generated by elements $s$, $t$, if a cycle ...
0
votes
0answers
31 views

Research topics related to cryptography and Hamiltonian cycles

I am very interested in pursuing a research where I can show an application of Hamiltonian cycles in Cayley graphs of some group such as reflection groups to the field of cryptography. But currently ...
1
vote
2answers
45 views

Which is the Cayley Graph of $\mathbb{Z}_2 * \mathbb{Z}_2$

I am trying to figure out how is the Cayley graph of the group $\mathbb{Z}_2 * \mathbb{Z}_2$. I think it should be a infinite tree, but I'm not sure because if $a$ and $b$ are the generators of this ...
1
vote
0answers
35 views

Elements of $C_3\rtimes C_2$ not $S_3$ or $D_3$

Can we represent an element of $G=C_3\rtimes C_2$ as $(a,b)$ like we do in the direct product? Because when I draw a Cayley diagram of $G$, I don't know how to label each node and arrow without the ...
0
votes
0answers
73 views

With reference to an argument related to a spanning path in a connected $4$-regular graph

I have a 4-regular odd ordered connected graph, say $X$. It is a vertex transitive graph, so there exists a perfect matching for the graph $X-v$, for any vertex $ v \in X$. There I consider two ...
0
votes
0answers
15 views

What types of graphs have good classical Ramsey properties?

This question is related to the search for classical Ramsey critical graphs. It is well known that circulant graphs have properties which make them good territory for finding these critical graphs. My ...
0
votes
0answers
18 views

Given Cayley Diagram of several groups,how to construct one for their product and quotient?

I know how to represent a group as a Cayley diagram.But problem arises when I deal with quotient or product of $2$ or more groups.I want to know the process of obtaining the Cayley diagram for product ...
1
vote
0answers
30 views

Number of vertices that are $l$ distance away from a given vertex in a Cayley Graph

Consider a Cayley graph $G=\mathbb Z/n$, under addition in $\mathbb Z$. Let $M$ be the set of generators such that $a\in M \implies -a \in M$. Suppose there are $m$ generators, so we may assume $G$ is ...
1
vote
1answer
68 views

What does the following Cayley diagram mean in Pinter's “A Book of Abstract Algebra”?

There is a problem in Pinter's "A Book of Abstract Algebra" (Chpt 9 Exercise D4) that has the following picture (some arbitrary group's Cayley Diagram representation): In fact, this picture is ...
2
votes
1answer
44 views

Cayley graphs on $n$ vertices

I would like to enumerate Cayley graphs ${\rm Cay}(G,C)$ on $n$ vertices. Since we have to choose a subset $C$ with $m$ elements out of the group $G$ (excluding identity) then there are ${n-1 \choose ...
1
vote
1answer
71 views

Cycles in Cayley graphs and group actions

I have recently begun studying geometric group theory and have a couple of basic questions about Cayley graphs. Given a (finitely generated) group $G$ with presentation $\langle x_{1},\ldots,x_{n}\...
4
votes
1answer
123 views

Question regarding Cayley graph generated in GAP software

I have computed a semidirect product of $(\mathbb{Z}_5 \times \mathbb{Z}_5) \rtimes \mathbb{Z}_3$ in GAP as shown below. ...
0
votes
0answers
36 views

Permutohedron Edge-Graph

I am learning about Permutohedron's and I am having trouble determining how vertices are connected by edges. Wikipedia tells us that the edge-graph of a permutohedron is the Cayley graph of adjacent ...
1
vote
1answer
51 views

How to draw automorphisms of a Cayley graph [closed]

In the figure below, I have drawn the undirected Cayley graph of the Cayley graph of $\mathbb{Z}_5 \times \mathbb{Z}_5$ with respect to the generating set $S=\{(0,1),(1,0)\}$. Can someone please ...
0
votes
0answers
61 views

Computing the multiplication of elements to generate the Cayley graph of a semidirect product

I have computed a semidirect product, $s$ of $(\mathbb{Z}_5 \times \mathbb{Z}_5) \rtimes \mathbb{Z}_3$ as below and have drawn a Cayley graph for $s$ with respect to a generating set $S$. But I wanted ...
1
vote
1answer
43 views

Automorphism of a Cayley graph [closed]

When considering the Cayley graph of $\mathbb{Z}_3 \times \mathbb{Z}_3$ with respect to the generating set $S=\{(0,1),(1,0)\}$, as shown in Figure (1) below, can I regard the graph in Figure (2) as ...
1
vote
1answer
67 views

1-ended Cayley graphs

I have been trying to understand the famous theorem for Cayley graphs, which states that, essentially, most infinite groups have a $1$-ended Cayley graphs (by characterizing precisely the cases in ...
3
votes
0answers
45 views

Understanding mapping of vertices in Cayley graphs of semidirect products

I came across a small question related to the Cayley graphs of semidirect products of the form $G=(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes \mathbb{Z}_q$. Consider $Cay(G, S_1)$, where $S_1=\{a,b,c\...
0
votes
1answer
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$ ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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>...
2
votes
0answers
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 ...
0
votes
1answer
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-...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
3
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
116 views

Degree or valency of a Cayley graph

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 ...
2
votes
0answers
51 views

Question regarding the factor group lemma for Cayley graphs

Can someone please explain the proof of the "Factor group lemma" for Cayley graphs which is stated below. Factor Group Lemma: Suppose that 1.$N$ is a cyclic, normal subgroup of a group $G$. 2.$(s_1,...
1
vote
2answers
79 views

A question related to the binding number of a graph

I came across with a definition for the "binding number" of a graph as below. $G$ is a graph and $V(G)$ is the vertex set of graph $G$. There it is mentioned as "min". Does that mean the minimum ...
2
votes
0answers
75 views

Diameter of Cayley graphs of symmetric groups

Let $S_n$ denote the symmetric group on $n$ letters. If we consider the Cayley graph $\Gamma(S_n,C)$, where $C=\{(12),(12\cdots n)\}$, is there any formula for calculating the diameter of $\Gamma(S_n,...