[Math] Number of orbits in a graph.

Question

I am confused with this concept. Consider for instance the graph:

$G$ with
$V=\{v_1,\dots, v_{10} \}$, $E=\{(1,2), (1,5), (1,6), (2,3), (2,7), (3,4), (3,8), (4,5), (4,9), (6,7), (7,8), (8,9), (9,10), (5,10), (6,10) \}$.

This is a 3-regular graph. If I understood correctly, there's only one orbit for this graph, the one with $\{v_1,\dots, v_{10} \}$.

However, this other graph (same vertex set, also 3-regular) :

$E=\{(1,2), (1,6), (1,7), (2,3), (2,7), (3,4), (3,8), (4,5), (4,8), (5,6), (6,9), (5,9), (7,10), (8,10), (9,10)\}$

has different orbits. Which would be for this case? Is there a guideline of how to find such orbits in a generic graph?

Answer 1

Summary : Drawing the graph is the best way I know of to find the orbits by hand. There are some computational ways, though.

Morgan Numbers

This may have a more mathematical name, but this is a technique from chemistry that's quite easy to do with small (non degree-regular!) examples. The algorithm is:

1. Label the vertices by degree.
2. Make a new label for each vertex from the sum of the labels of the neighbours.
3. Repeat until the number of different labels no longer changes.

To put it another way, we are forming a kind of 'extended degree' for each vertex by recursively summing the degrees of neighbours. Note : Naturally this does not work for degree-regular graphs!

From the Automorphism Group

This may be the 'very tedious' approach mentioned in the comments, but given the automorphisms of the graph, you can run through each automorphism in turn, checking if it carries one element to another and putting them in the same orbit. There may be more efficient algorithms, but I don't know of them.

Using Signatures

I can not resist mentioning Signatures which are a technique for producing a canonical form of a graph; particularly molecular graphs, which are vertex- and edge- labelled. While it is technically possible to do this on paper, it gets very tiresome for large graphs, and is probably no better than just drawing it.

For example, your second graph has the following signatures, with the orbits following each:

[1, 2, 3, 4, 5, 6] = [.](-[.](-[.](-[.,0](-[.,1])-[.,3])-[.,3](-[.,2]))-[.](-[.](-[.,0]-[.,1])-[.,4])-[.,4](-[.,2](-[.,1])))
[7, 8, 9] = [.](-[.](-[.](-[.,2]-[.,1](-[.,0]))-[.](-[.,3]-[.,0]))-[.](-[.,2](-[.,1])-[.,4])-[.,4](-[.,3](-[.,0])))
[10] = [.](-[.](-[.](-[.,1]-[.,2])-[.,1](-[.,4]))-[.](-[.,2](-[.,3])-[.,3](-[.,0]))-[.](-[.,4](-[.,0])-[.,0]))

As you can see, they are not very readable - but they do get the expected answer...