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

3
votes
0answers
30 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
25 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
0answers
105 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
52 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
106 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
108 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
169 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
61 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
70 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
97 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.
0
votes
0answers
35 views

How to choose the adjacency set

Given a group $G$ of order a composite number, how should one construct the adjacency set $S$ such that the underlying Cayley graph $\Gamma=\text{Cay}(G,S)$ admits a block system under ...
2
votes
0answers
90 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
71 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
64 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
170 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
118 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
87 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
180 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')$ ...