#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):
Replying to [comment:81 ncohen]:
> > Do you find any flaw in the above argument? Also, can you provide the
graphs which you claim to be counterexamples?
>
> I agree with you everywhere short of one thing: if the graph you started
with is not connected, then the set you are talking about is not a
*generating* set, e.g. : take the disjoint union of two cliques of size n,
and as a regular subgroup take two disjoint cycles of order n plus a
reflections that exchanges both.
In this case the set does not generate the group, but it still is a
generating set in the sense that it generates the graph. In any case,
disconnected graphs are given a special treatment, checking Cayleyness
only for a connected component.
Now, whether we allow Cayley graphs to be disconnected is just a matter of
definition. I know that usually they are assumed to be connected, but in
my opinion we should allow disconnected graphs to be called Cayley (it
even allows this method to make optimizations by looking at complements).
So the example you gave above is fine without raising an exception IMO.
Janoš
--
Ticket URL: <http://trac.sagemath.org/ticket/19586#comment:82>
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.
