#19586: Add is_cayley_graph
-------------------------------------+-------------------------------------
Reporter: jaanos | Owner:
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-7.1
Component: graph theory | Resolution:
Keywords: Cayley graphs | Merged in:
groups | Reviewers: Nathann Cohen
Authors: Janoš Vidali | Work issues:
Report Upstream: N/A | Commit:
Branch: | a58a7348bc022f39bf68383b70400e8b7f5b268b
u/jaanos/add_is_cayley_graph | Stopgaps:
Dependencies: |
-------------------------------------+-------------------------------------
Comment (by jaanos):
Hi!
Let's see... if the automorphism group has a regular subgroup `G`, then we
can pick any vertex `w` and construct a bijective mapping that maps a
group element `g` to the vertex `g^w`. Now, suppose we have an arc `uv`
such that group elements `g` and `h` map to `u` and `v`, respectively.
Then we may label the arc by `e = g^-1 h`, and any automorphism `a` from
`G` will map `uv = g^w h^w` to `(ag)^w (ah)^w`, i.e. an arc with the same
label. Since such a graph is necessarily vertex-transitive, it follows
that the (multi)set of labels on arcs starting in a vertex is independent
of the choice of said vertex. The Cayley graph of `G` with said (multi)set
as its generating set is then isomorphic to our graph.
Do you find any flaw in the above argument? Also, can you provide the
graphs which you claim to be counterexamples?
Janoš
--
Ticket URL: <http://trac.sagemath.org/ticket/19586#comment:78>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
