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

4
votes
1answer
59 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
72 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
67 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
22 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
48 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
23 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
74 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
36 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
55 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
30 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
136 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
61 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
144 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
143 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
210 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
72 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
81 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
109 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
113 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
83 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
70 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
182 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
182 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
96 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
189 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')$ ...