1
$\begingroup$

Typically Cayley graphs are defined for groups and generators sets S. But basically one only needs some set S and another set V and partially defined operation SxV->V, then one defines graph with vertices V and one have an edge between $v_1,v_2$ if there exists $s \in S: v_1=sv_2$. So for definition nothing is required - neither associativity, neither identity and so definition works various types of algebraic structures: groupoids, monoids, quasigroups, etc...

The famous Lovász conjecture predicts existence of the Hamiltonian path for Cayley graphs of arbitrary finite groups.

Question 1: Are there any results or expectations when we somehow relax group condition to groupoid, loop, semigroup, or whatever...

Question 2: In particular graphs of states/transitions for famous 15-game or its NxN analogs, or other sliding puzzles or M13 Mathieu groupoid by Conway - are they expected to contain a Hamiltonian path ?

Question 3: One can also take Octonions, Sedenions, Pathions, Chingons (etc. by Cayley–Dickson construction ) take their units and construct "Cayley" graphs from these units - same question .

All graphs are considered undirected. (Any information for directed graphs is also welcome, but it is already known for groups that directed Hamiltonian paths not always exists).

Improve this question
$\endgroup$
4
  • $\begingroup$ The graph might not be connected. For instance take a right zero semigroup with two or more elements and you get either an edge free graph or loops at the vertices $\endgroup$
    – Benjamin Steinberg
    Commented May 28 at 22:52
  • $\begingroup$ In any event it is not natural to use unidirected graphs with no inverses. $\endgroup$
    – Benjamin Steinberg
    Commented May 28 at 22:54
  • $\begingroup$ Yes, sure we can have many connected components, so we can for each of them or for some. $\endgroup$
    – Alexander Chervov
    Commented May 28 at 23:11
  • $\begingroup$ Well it depends , e.g. you can embed in object with inverses . If not does it imply - no Hamiltonian path ? So there is kind of degrees of freedom... $\endgroup$
    – Alexander Chervov
    Commented May 28 at 23:16

0

Reset to default

You must log in to answer this question.