#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: |
-------------------------------------+-------------------------------------
Changes (by dimpase):
* status: needs_review => needs_info
* milestone: sage-6.10 => sage-7.1
Comment:
I probably don't understand something, but why is the existence of a
regular subgroup sufficient for the graph to be Cayley? Indeed, one seem
to need in addition that this subgroup is generated by the elements
corresponding to the neighbours of a vertex.
E.g. I can construct a cubic, arc-transitive, digraph on 16 vertices, with
a regular subgroup being elementary abelian, i.e. in particular having 4
generators. The underlying graph has degree 6, so it is OK as a Cayley
graph, but not OK as a Cayley digraph, as 3 generators (the out-degree of
the digraph) are not enough!
----
New commits:
||[http://git.sagemath.org/sage.git/commit/?id=34f921203675100401cd514d41e5605d0bfb9683
34f9212]||{{{Check for Cayleyness of the complement if the graph is simple
with density > 1/2}}}||
||[http://git.sagemath.org/sage.git/commit/?id=d5b8bc7aab040920ba51c9a250b5600fccb4e629
d5b8bc7]||{{{trac #19586: Merged with 7.0}}}||
||[http://git.sagemath.org/sage.git/commit/?id=278bb474d1d17f15f673e9be2e41cca144aacea0
278bb47]||{{{trac #19586: Review}}}||
||[http://git.sagemath.org/sage.git/commit/?id=a58a7348bc022f39bf68383b70400e8b7f5b268b
a58a734]||{{{Merge branch 'public/19586' into is_cayley_graph-gap}}}||
--
Ticket URL: <http://trac.sagemath.org/ticket/19586#comment:72>
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.
