2
$\begingroup$

Let's say we have a sketch of an underected graph like the one below:

graph permutation

And we are told to count the ways we can seat 5 people on those chairs (if the vertices are chairs). So this is a permutation problem, with the condition that we have some symmetries in the arrangement of the chairs, so that if we neglect the symmetries, we may count some cases more than once (which is not correct).

If, instead of the graph above, we had a cycle (like a ring) $C_n$, then I would say that there are $\frac12 (n-1)!$ ways to seat those people on the chairs (the vertices of $C_n$). But how can we make a permutation formula for new graph sketches like the one above?

Any idea? Are there any rules of thumb which are useful? or an algorithm?

$\endgroup$
2
$\begingroup$

Arthur’s answer shows how to calculate this for your specific case, but doesn’t mention the tools you need to generalize this, so I wanted to expand on his answer a bit.

The concept we need to understand to approach this problem in general is the automorphism group of a graph, $\text{Aut}(G)$. The number of distinct ways to label a graph, up to isomorphism is always given by $$\frac{n!}{|\text{Aut}(G)|}.$$

Calculating the size of the automorphism group of a graph in general is hard(it is at least as hard as the graph isomorphism problem.) but almost all graphs have trivial automorphism group, so for some applications this can be circumvented.

Edit: For more information about the automorphism group of a graph, you can check out: http://mathworld.wolfram.com/GraphAutomorphism.html

or: https://en.m.wikipedia.org/wiki/Graph_automorphism

$\endgroup$
  • $\begingroup$ Thank you. This gave me the general idea I wanted; finding the automorphism group of small graphs is not very hard. Also, I found some useful things in mathworld.wolfram.com/GraphAutomorphism.html, It would be better if you add this like to your answer. $\endgroup$ – AHB Nov 25 '17 at 9:35
  • $\begingroup$ @AHB I added that link and one other. $\endgroup$ – Sean English Nov 25 '17 at 22:15
1
$\begingroup$

The number of essentially distinct seating arrangements is $n!$ divided by the number of permutations that you consider would give rise to "the same" configuration. For instance, for the cyclic case, the are $2n$ such transformations ($n$ rotations, and $n$ reflections).

In your case, there are $8$ permutations (the top left vertex is special, and the remaining four give $C_4$, which by the above gives $4+4=8$), so there are $120/8=15$ essentially different seating arrangements.

$\endgroup$
  • $\begingroup$ This was the method of dealing with that graph above, but I want some idea of what we should be seeking if we are given a completely new (but not much messy) graph sketch. $\endgroup$ – AHB Nov 25 '17 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.