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

### comment:2 follow-up: ↓ 3 Changed 5 years ago by

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

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.

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