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
4
votes
2answers
84 views

Automorphisms of Cayley graphs of $\mathbb{Z}$

My goal is to show that there are no finite generating sets $A$ and $B$ such that $\mathrm{Cay}(\mathbb{Z},A)$ is isomorphic to $\mathrm{Cay}(\mathbb{Z}\times \mathbb{Z}_2, B)$. My idea for this is to ...
0
votes
0answers
20 views

Relation of the product of elements in the quotient graph to two Hamiltonian cycles differing in one edge

Lemma: Let $G$ be a finite group and $S$ be a generating set of $G$. Suppose, $N$ is a cyclic normal subgroup of $G$ $(s_1N, \cdots , s_n N)$ is a Hamiltonian cycle in $Cay(G/N,S)$ the product $s_1 ...
0
votes
1answer
44 views

A Cayley graph of the quaternion group of order 12 [closed]

Let $Q_{12}=\langle a,b \mid a^6=1, a^3=b^2, ba=a^{-1}b\rangle$ be the quaternion group of order $12$. Let us consider the Cayley graph $G={\rm Cay}(Q_{12},\{a^{\pm 1},b^{\pm 1}\})$. Is this graph ...
2
votes
0answers
34 views

The Hamiltonian cycle in a Cayley graph whose corresponding group has a finite cyclic normal subgroup [closed]

Let $S$ generate a finite group $G$ and $s \in S$ such that $\langle s\rangle \trianglelefteq G$, ${\rm Cay}(G/\langle s\rangle,S)$ has a Hamiltonian cycle. Let $(s_1,s_2, \cdots, s_n)$ be the ...
0
votes
0answers
16 views

Hamiltonian cycles in a quotient graph and original graph

I am currently reading regarding Hamiltonian cycles and I came across the following. "Suppose, $N$ is a cyclic normal subgroup of $G$, such that $|N|$ is a prime power. $<s^{-1}t> = N$, ...
0
votes
1answer
53 views

Using PlotGraph command from JupyterViz in MyBinder [closed]

I am executing a program "Newprogram.gap" in GAP file in My Binder. There, I have an output which is an adjacency matrix, $A$ corresponding to a Cayley graph. 1). I need to add the command &...
1
vote
1answer
24 views

Sequence of elements representing a Hamiltonian cycle and the generating element of a subgroup

Let $S$ be a subset of a finite group $G$. The Cayley graph $Cay(G,S)$ can be defined as the graph whose vertices are the elements of $G$, with an edge joining $g$ and $gs$, for every $g \in G$ and $s ...
1
vote
2answers
38 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 ...
0
votes
1answer
62 views

Cayley graph of an infinite group using GAP

I have a finitely presented group which is infinite, and I wish to create a visual representation of its Cayley graph using GAP. If possible I would like to do this using YAGS package. My group is $\...
1
vote
0answers
37 views

Cayley Graphs 1-factorization 4-cycles

Let $X$ be a connected graph on $2^n$ vertices for $n ≥ 1$. Prove that $X$ is a Cayley graph of $\mathit{Z}\,_n^2$ if and only if X has a $1$-factorization such that the union of any two $1$-factors ...
0
votes
0answers
48 views

visualization of Cayley graph in GAP [duplicate]

I want to draw a Cayley graph of a group using GAP after I get a list. Is there a way to visualize that Cayley graph ? Or is there any other software to do it?
2
votes
1answer
140 views

Cayley graphs obtained for different generating elements with the same orders in a finite group

When we consider the finite group $\mathbb{Z}_p \times \mathbb{Z}_p$, where $p$ is a prime, $p>2$, the set with the pair of elements $\{(0,1), (1,0)\}$ can generate the group. Moreover, a set $\{(1,...
2
votes
1answer
45 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 ...
-1
votes
1answer
17 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 ...
2
votes
0answers
21 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 ...
0
votes
1answer
44 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. ...
3
votes
1answer
45 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 ...
2
votes
1answer
62 views

Automorphism group of a Cayley graph

Let $G$ be a group. Let $\Gamma = \Gamma(G,X)$ be the Cayley graph of $G$ defined with respect to a generating set $X$. I want to show that $G\cong \text{Aut}(\Gamma)$. Note that by $\text{Aut}(\Gamma)...
0
votes
0answers
60 views

What are the advantages of Hamiltonian paths/cycles in Cayley graphs when considering their applications

If a function (like a hash function) maps a vertex of a connected Cayley graph to another vertex which will be the ending point of a Hamiltonian path, is there a particular advantage over a function ...
0
votes
0answers
22 views

Determining the automorphism of a vertex transitive/Cayley graph which will map a vertex to another given vertex under some conditions

A Cayley graph is a vertex-transitive graph, meaning that given any two vertices $v_1, v_2$ in the vertex set of the graph $X$ ($V(X)$), there exists an automorphism $\phi:V(X) \rightarrow V(X)$, such ...
3
votes
0answers
46 views

Geometric Interpretations of the Automorphism Group of a Group?

I saw this question recently, which asks for a "geometric" example where a certain automorphism doesn't exist. Since some counterexamples are well known, I thought it should be a simple task ...
0
votes
0answers
9 views

Tracing a relationship which appears to be corresponding to a cycle, along the graph to check whether it indeed is a cycle

I have a Cayley graph generated by the generating set $S=\{g_1,g_2\}$, where $S$ is inverse closed and a relationship between these generating elements, $g_1 ^{x_1} g_1 ^{-x_2} g_2^{x_3} g_2^{-x_4}=e$....
1
vote
0answers
30 views

Number of each generating elements of the Cayley graph appearing in a Hamiltonian cycle

Let $G$ be a finite group and $S$ be a subset of $G$. Let the Cayley graph of $G$ with respect to $S$ be $Cay(G,S)$, provided that $1 {\not\in} S$ and $S$ is inverse closed. Consider the Cayley graph ...
0
votes
0answers
32 views

Code for commands in GAP [duplicate]

Is there a way we can check and refer the source codes which execute the commands like "CayleyGraph()", "SemidirectProduct()" which are used for computations in GAP software?
0
votes
1answer
31 views

Every Cayley graph is vertex transitive

I cannot come up with a proof of the following statement (which is true according to wikipedia): Every Cayley graph is vertex-transitive. Can anyone enlighten me? Thanks!
0
votes
0answers
49 views

Show that a Cayley digraph is strongly connected if and only if it is weakly connected.

Show that a Cayley digraph is strongly connected if and only if it is weakly connected. (A digraph is strongly connected if there is a directed path between any two vertices. It is weakly connected if ...
4
votes
1answer
197 views

Application of Cayley’s theorem in Sylow’s theorem

I’ve just started reading Sylow’s theorems. I have heard that Cayley’s theorems are applied in Sylow’s theorem. Can someone exactly point out where in the three Sylow’s theorem is Cayley’s theorem ...
0
votes
1answer
72 views

Number of undirected trees with unlabled vertices and labeled edges

I would appreciate some help coming up with an expression for the number of spanning trees of an undirected graph with m labeled edges but m+1 unlabled vertices. The answer is supposed to be ${m+1}^{...
2
votes
0answers
110 views

general properties for Cayley graphs of hyperbolic triangle groups

Is it possible to derive some general properties for Cayley graphs of hyperbolic triangle groups, presented as $$ \langle a,b,c | a^2=b^2=c^2=(ab)^p=(bc)^q=(ca)^r=1\rangle \text{, with } \frac1p+\...
1
vote
2answers
50 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, ...
3
votes
0answers
85 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
133 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
67 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
28 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
33 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
33 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
0answers
32 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
47 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 ...
2
votes
0answers
29 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
15 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
28 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
31 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 ...
1
vote
2answers
79 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
37 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 ...
1
vote
0answers
34 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
85 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
49 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
157 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
202 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
71 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 ...