1
$\begingroup$

I have group $G$ acting on a 4-regular 120 node graph $\Gamma$. I want to compute equivalence classes of connected subgraphs of $\Gamma$, where by equivalent I mean in the same orbit. More specifically I want a list of representatives for each equivalence class.

Are there any known algorithms for such computations?

P.S. I am able to do this in small cases by naive brute force because I enumerate all the subgraphs.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Given that there are at least $2^{121}$ connected subgraphs, probably you need to reduce your aims. Are you after some very limited type of subgraph perhaps? And how large is the group? $\endgroup$
    – Brendan McKay
    Commented Jun 15, 2016 at 3:38
  • $\begingroup$ @BrendanMcKay I am depressingly aware of the large number of subgraphs but I don't want every one of them. Initially I wanted isomorphism classes of subgraphs, but due to a (for lack of a better term) "chirality" consideration, this is too coarse and I need representatives of the orbits (perhaps ismorphism classes are the place to start?). The group is $A_5$, the alternating group on $5$ letters. $\endgroup$
    – Bill B
    Commented Jun 15, 2016 at 15:14
  • $\begingroup$ Since the group is quite small, just look at each labelled subgraph that is of interest and reject it if it is not the smallest of its 60 images under the group. Define "smallest" however you please (any total order on labelled graphs). The average number of tests per subgraph will only be about 2, so this is quite efficient. $\endgroup$
    – Brendan McKay
    Commented Jun 15, 2016 at 22:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .