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

2
votes
0answers
43 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
17 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
65 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
32 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
31 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
32 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
52 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 ...
0
votes
1answer
28 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 ...
6
votes
1answer
129 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
58 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 ...
6
votes
1answer
123 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
127 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
194 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
66 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
78 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
104 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
106 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
78 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 ...
1
vote
2answers
68 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 ...
8
votes
1answer
180 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
137 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
89 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
185 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')$ ...