Opened 5 years ago

Last modified 5 years ago

#17611 new enhancement

Add option to enable testing actions of subgroups of graphs

Reported by: azi Owned by:
Priority: minor Milestone: sage-6.5
Component: graph theory Keywords:
Cc: ncohen, nt.a.am1392@… Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

As Nathann remarked when we were doing the graph symmetry tests it could make sense to add an optional argument to is_vertex_transitive & friends passing the automorphism group. That would be make great sense in order to reduce the number of times the automorphism group is computed in, say the function is_semi_symmetric.

For some reason I've received many emails of people asking how to check if a graph G is H-*-transitive for a subgroup H of Aut(G). That would of course already be covered if we include the caching thing.

I am too busy to do that myself right now and I am leaving this as an easy TODO ticket in case anyone is willing to do it.

Change History (3)

comment:1 Changed 5 years ago by ncohen

Perhaps we should just cache the result of .automorphism_group(), given that we have immutable graphs. And we could have notes in the related functions saying that it uses the cache if the graph is immutable ?

Nathann

comment:2 follow-up: Changed 5 years ago by azi

Yes this looks like a good way to do it. Though it we would then need to address separately this new feature of testing transitivity on subgroups of Aut(G) ?

comment:3 in reply to: ↑ 2 Changed 5 years ago by ncohen

Yes this looks like a good way to do it. Though it we would then need to address separately this new feature of testing transitivity on subgroups of Aut(G) ?

Sorry, I answered on this ticket the first paragraph of the ticket's description, but they are different issues.

I do not believe that the computation that you mention is really a graph feature.... It feels much more like a PermutationGroup method: we already have AG.is_transitive(domain=X) which tests if AG is transitive on X. We could add to it what AG.orbit already handle, i.e. orbits of pairs, tuples, etc ...

Nathann

Note: See TracTickets for help on using tickets.