All Questions
7 questions
1
vote
1
answer
80
views
What are the efficient algorithms to compute Hamiltonian paths on Cayley graphs of finite groups ? Can GAP do it?
The famous Lovasz conjecture predicts existence of the Hamiltonian path on Cayley graphs. In general finding such a path is NP-complete problem, but there are many heuristic algorithms.
Question 1: ...
- 24.9k
12
votes
1
answer
1k
views
Necessary and sufficient conditions for the Cayley graph to be bipartite
Let $G$ be a finite group with identity $1$. If $S$ be an inverse closed generated subset of $G$, then $S$ is called a Cayley subset of $G$.The Cayley graph $\Gamma=\operatorname{Cay}(G, S)$ is a ...
- 173
-1
votes
1
answer
215
views
Perfect Cayley graphs for abelian groups have $\frac{n}{\omega}$ disjoint maximal cliques
Let $G$ be a perfect/ weakly perfect Cayley graph on an abelian group with respect to a symmetric generating set. In addition let the clique number be $\omega$ which divides the order of graph $n$. ...
- 2,089
4
votes
2
answers
485
views
Transposition Cayley graphs are planar
Consider the Cayley graph $G$ with vertex set the elements of the symmetric group $S_n$ and generating set the set of minimal transposition generators of the group $S_n$, that is the set $S=\{(12),(13)...
- 2,089
5
votes
1
answer
385
views
$C_4\times C_2 : C_2$: what does this mean?
I am reading this paper where the object $C_4\times C_2 : C_2$ is used as a group structure. I know that $C_n$ is a cyclic group but don't know what kind of operation between groups is identified by ...
- 219
5
votes
1
answer
275
views
Diameter of Cayley graphs of finite simple groups
Babai, Kantor and Lubotzky proved in 1989 the following theorem (Sciencedirect link to article).
THEOREM 1.1. There is a constant $C$ such that every nonabelian finite simple group $G$ has a set $S$ ...
- 237
11
votes
4
answers
1k
views
Is there a Cayley graph of a non-abelian finite group that is not isomorphic to any Cayley graph of any abelian group?
It's the first question I post here :) I'm sorry if the question is too specific or if it's somehow repeating others.
In other words, my question is the following. Consider a Cayley graph $\Gamma$ of ...
- 111