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

learn more… | top users | synonyms

1
vote
0answers
29 views

Which of these Cayley graphs are isomorphic? (Pinter, Book of Abstract Algebra, Chapter 9)

Work so far (please correct if wrong): I think none of them are isomorphic to each other except for maybe the bottom two. My real question is: What kind of group would the last one (the solid ...
3
votes
1answer
47 views

Cayley graphs of groups

(Directed & undirected) Cayley graphs of groups have been studied a lot in the literature. I would like to know the answer to the following questions. Please give your valuable suggestions. Is ...
1
vote
0answers
16 views

Adam isomorphism of circulant graphs

Let $C(n; S)$ denote a circulant graph on $n$ vertices (the vertices can be labeled $0,\ldots,n-1$), and connection set $S = \{s_1, \ldots, s_k \}$. Let $1 \leq \mu < n$ be relatively prime to $n$. ...
3
votes
0answers
49 views

What is the diameter of the Cayley graph of $S_n$ w.r.t the generator $\{(12),(23),…,(n−1n)\}$?

Given a symmetric group $S_n $ and the generator set : $S = \{(12),(23), . . . ,(n − 1 n) \}$ is there any closed form expression for the diameter of the Cayley graph generated by this set of ...
1
vote
3answers
79 views

How to find the number of spanning trees for a cube?

Can you tell me a way of finding the total number of spanning trees in a $Q_d$ undirected labelled graph for $d = 3$. I know that the answer is 384, but the way (I know there are many.) of finding ...
0
votes
0answers
31 views

What is the Schreier graph of this group/subgroup/generating set?

Let $G=\langle Pa, b\mid a^3 = \mathrm{id}, (ba)^2 = \mathrm{id}\rangle $, $H = \langle b\rangle$ , and $S = \{a, b\}$. I have been trying to figure out what elements are in this group by finding the ...
1
vote
3answers
77 views

Cayley graph is a tree iff group is free

I am looking at this proof of this claim that the cayley graph is a tree iff g is a free group with generating set S. For the direction '$\implies $' I see that they have assumed that there are two ...
0
votes
1answer
98 views

Proving the continuation of the Cayley-Hamilton theorem from Schur's triangularization theorem

The Cayley-Hamilton theorem says that every square matrix can satisfy its own characteristic equation, $p(\lambda) = 0$, or $p(\mathbf{A}) = \mathbf{0}$. The question is to show how the ...
2
votes
1answer
86 views

About Cayley graphs on finite fields.

If one is given $n$ vectors of length $n$ $\in \mathbb{F}_{p^k}^n$ for some prime number $p$ and $k \in \mathbb{Z}^+$ then how can one check if they are linearly independent? (the issue is if there ...
0
votes
1answer
66 views

left and right multiplication for Cayley graphs

Correct me if i am wrong but i have written down the following: If $X$ is a finite group, with subset $S$ and corresponding Cayley graph $G$ The edge set for a Cayley graph is defined such that two ...
2
votes
3answers
74 views

Clear up definition of cayley graph

I have come across two definitions of Cayley graphs, both very similar but one being more general. I have been working with the more general definition which is: A Cayley graph of a group 􏰎$X$ ...
2
votes
1answer
69 views

Decomposition of a group whose Cayley graph is a tree

This is an exercise taken from Chapter 9 of a French book, Géométrie et Théorie des Groupes. It says, roughly, the following: Show that a finitely generated hyperbolic group, whose Cayley graph is a ...
1
vote
1answer
94 views

Drawing a directed graph in Maple

I have been playing around with some Maple today for a semigroup/ graph theory style project. I want to draw a left cayley graph with vertices $\{1,....,12\}$ and edges $[5, 5]$, $\{[6, 2].[7, 1], [1, ...
1
vote
1answer
23 views

Is the Cayley graph of a free group dense on the Poincare disc?

In other words, every point inside the disc corresponds to a word (possibly of infinite length) of the free group; Is that correct? With this embedding:
0
votes
0answers
55 views

Svarc-Milnor Lemma to prove that finite index subgroup of f.g. group is finitely generated

I found a proof using Švarc-Milnor lemma (the Lemma is prop. 1.19 here) of the well known fact that a subgroup of finite index of a finitely generated group is finitely generated (here a proof with ...
0
votes
1answer
38 views

Proof of a Cayley graph result.

I am searching now for the most explicative and easy understand in this level (I am a second year student) proof of the following result: A Cayley graph is connected iff S generates G where G is a ...
0
votes
1answer
35 views

What is the notion of “character” in the context of Cayley graphs?

I am looking at these notes, http://www.eecs.berkeley.edu/~luca/books/expanders.pdf On page 37, Lemma 5.16, the notion of "character" defined seems to be any map from the finite Abelian group to ...
0
votes
0answers
22 views

Question of Cayley graphs of certain group

I want to draw the Cayley graph of $S_4$ with respect the rotations of the cube 90º with respect the y axis (is the one pointing up and I will call it $g_1$) and with respect the x axis (the one ...
2
votes
1answer
58 views

Factor Group Lemma of Cayley Graph

Factor Group Lemma: Suppose that 1.$N$ is a cyclic, normal subgroup of group $G$. 2.$(s_1,s_2,\ldots,s_m)$ is a hamiltonian cycle in $Cay(G/N;S). 3.The product $s_1s_2\cdots s_m$ generates $N$. ...
2
votes
1answer
73 views

Did I map this group right?

I am trying to get a group with 8 elements. This is a Cayley table of $\mathbb Z_2 \times \mathbb Z_4$. Is this right? $$ \begin{array}{c|cccc} & 1 & 2 & 3 & 4\\ \hline 1 & 1 ...
6
votes
1answer
93 views

on Cayley diagrams

is the picture the Cayley Graph of the group $\langle a,b,c\mid a^2, b^2,c^2\rangle$ ? What would it be for $\langle a,b,c\mid a^2b^2c^2\rangle$?
1
vote
2answers
90 views

Proof: directed cycle?

A directed cycle graph is a directed version of a cycle graph, with all the edges being oriented in the same direction. In a directed graph, a set of edges which contains at least one edge (or arc) ...
1
vote
1answer
98 views

Cayley graphs of finite 2-generator groups

Let $G=\left<a,b\right>$ be a finite 2-generator group and $\Gamma$ its Cayley graph with respect to $\{a,b\}$. Is it true that $\Gamma\setminus\{e,f\}$ is connected for two arbitrarily chosen ...
0
votes
1answer
32 views

Are These Graphs Circulant?

We will say a circulant graph is a graph whose adjacency matrix is circulant (even if the graph is disconnected). Let $R$ be a Dedekind domain, and let $I$ be an ideal of $R$ such that $R/I$ is finite ...
2
votes
0answers
59 views

s4≀s2 visually?

What does the polytope whose symmetry is (exactly, not larger isomorphisms) s4≀s2 look like? Does anyone know of a full decomposition of its construction, i.e. lattices, hasse diagrams, cayley graphs, ...
1
vote
1answer
27 views

Clarification from a proof that a certain type of graph can be endowed with a group operation

I need some help sorting out a construction of a group out of the vertices of a digraph with a certain property. I'll just throw some definitions here first... Definitions. An alphabet ...
3
votes
3answers
108 views

Viewing an abelian group using cayley diagram

I cannot understand this way of viewing whether a group is abelian using cayley's diagram: (from Visual group theory book) What I can't understand is that while checking being abelian we check ...
1
vote
1answer
45 views

Order of an element in direct product using cayley's diagram

How can I find the order of element (1,1) of the group $C_4\times C_3$ visually in the diagram below :
1
vote
1answer
46 views

Elements in the same coset and the Cayley Diagram

A question from Visual group theory, by Nathan Carter. In a Cayley diagram, if $aH$ is a coset of a subgroup $H$ of a group $G$ and $b$ belongs to $aH$, why is it that every node that can be reached ...
3
votes
0answers
40 views

Diameter of undirected graph

Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we remove the orientation of the arcs, thus getting an undirected graph $G'$ with diameter $D'$. Obviously, $D' \leq ...
0
votes
0answers
61 views

How many trees, not necessarily spanning, are there with exactly m edges and n vertices?

I've been struggling with this combinatorical question and got very confused: Given $n$ vertices: $\{v_1,v_2,\ldots,v_n\}$, in how many ways can a tree be assembled upon them, not necessarily ...
1
vote
1answer
69 views

Cayley graph of an amalgam

I was wondering what the Cayley graph of an amalgam $A*B$ (over $\{ 1\}$ ) is? $A, B$ are finitely generated. Can't work it out.
0
votes
1answer
62 views

Ramanujan (LPS) graph construction

In the original LPS article they mention two constructions for Ramanujan graphs, one with order $q^3$ nodes and the other in order $q$. My question is regarding the second construction (which is ...
8
votes
1answer
186 views

Applications of Cayley Graphs in Physics

I have been recently reading about Cayley graphs and character theory. It is evident that Cayley graphs are very useful tool in theoretical computer science. In physics, Cayley graphs seem do appear ...
2
votes
1answer
69 views

Quasi-isometry of Schreier coset graphs

Let $G$ be a finitely generated group and $H$ a subgroup. For any choice of a generating set $X$ we can form the Schreier coset graph. Is this graph independent of the generating set up to ...
1
vote
0answers
43 views

A Question about Cayley Graph [duplicate]

Petersen graph is this graph: Petersen graph can not be a Cayley graph. How to prove that? Can someone give a general method to judge a graph is or not a Cayley graph?
6
votes
1answer
218 views

What does the Cayley graph of the Grigorchuk group 'look like'?

I've recently renewed my interest in tilings, and as a result have taken some splashes into Word Processing in Groups (in search of good information on the automatic groups related to hyperbolic ...
2
votes
1answer
234 views

Software for generating Cayley graphs of $\mathbb Z_n$?

Does it exist any program (for linux) which can generate a nice Cayley graph of any $\mathbb Z_n$? (If it's possible to create such a graph at all, that is.) (where perhaps $n ≤ 100$ or something ...
1
vote
4answers
235 views

Without using Cayley’s theorem, prove that there are at most $n^{2n−2}$ labelled trees with n vertices.

I am studying for a test I have and I found a past problem which I have no idea how to go about doing.. My thoughts are. I know not to use Cayley's theorem but it says that there are $n^{n-2}$ ...
1
vote
0answers
88 views

number of ways to obtain a given permutation from k swaps

Let $\sigma_1, \ldots, \sigma_b \in S_n$ be all the 2-cycles ("swaps") in $S_n$. (So, $b = \binom{n}{2}$.) Given some $\pi \in S_n$, is there a known formula for how many ways to obtain $\pi$ as a ...
2
votes
1answer
96 views

Make $3$-hypergraph Cayley on $ D_{2n} $ and $ \mathbb Z_n$

How we can make $3$-hypergraph Cayley on $ D_{2n} $ and $ \mathbb Z_n$? Definition: let $G$ be a group, A $3$-hypergraph cayley on $G$ has a generator set $T$ with elements of order $3$ such that ...
1
vote
3answers
134 views

Cayley graph on $ D_{2n} $ and $ \mathbb Z_n$

How we can make Cayley graph on $ D_{2n} $ and $ \mathbb Z_n$? What can be S in $Cay(D_{2n},S)$ and $ Cay(\mathbb Z_n ,S)$, Please write one example. Thanks for advise.
2
votes
0answers
139 views

Representing digraphs by undirected graphs

One can represent every group as a directed graph with colored edges (its Cayley graph). Identifying the colors of the edges with specific vertices of the graph (its generators), one ends up with a ...
3
votes
0answers
103 views

Line graph of Cayley graph of $\mathbb{Z}_2^3$ is $A_4$

Consider the group $G=\mathbb{Z}_2^3$ with generators $S=\{e_1,e_2,e_3\}$ with $e_1=(1,0,0),e_2=(0,1,0),e_3=(0,0,1)$. The Cayley graph $\text{Cay}(G,S)$ is the 3D hypercube graph. It's line graph ...
2
votes
2answers
79 views

Can we get the line graph of the $3D$ cube as a Cayley graph?

Given a graph $G=(V,E)$, the line graph of $G$ is a graph $\Gamma$ whose vertices are $E$ (the edges of $G$) and in $\Gamma$, two vertices $e_1,e_2$ are connected if, as edges in $G$, they share an ...
10
votes
1answer
634 views

Petersen graph is not a Cayley graph

How can I show that the Petersen graph is not a Cayley graph? I don't know very much about Cayley graphs, I know that they are vertex-transitive, but so is the Petersen graph. It probably has to do ...
8
votes
1answer
214 views

Computing shortest paths in Cayley graphs

I am interested in shortest paths in the Cayley graph of the alternating group $A_{12}$ acting on the vertices of the icosahedron, where the generators are given by 5-cycles on the neighbors of any ...
0
votes
2answers
220 views

Prove that k-cube graph is a Cayley graph

Define Cayley graph as following: G is finite group. C $\subseteq$ G such that C does not contain identity element of G and g-1 $\in$ C for all g $\in$ C. Cayley graph X(G,C) is formed with vertices ...
2
votes
1answer
110 views

How to form Cayley graph from group

Define a Cayley graph as follows: $G$ is finite group. $C \subseteq G$ such that $C$ does not contain identity element of $G$ and $g^{-1} \in C$ for all $g \in C$. Cayley graph $X(G,C)$ is formed ...
4
votes
1answer
233 views

Cayley graphs on small Dihedral and Cyclic group

Consider the following problem Let $n \leq 5$ and let $\Gamma = \mathrm{Cay}(C_{2n},S)$ be the Cayley graph with Cayley set $S$. Show that $\Gamma$ is isomorphic to $\mathrm{Cay}(D_{2n},S')$ ...