0
$\begingroup$

I know there will be 9 vertices of degree 6, which means there are 54 edges. But then how will I figure out the number of non-isomorphic graphs?

$\endgroup$
  • $\begingroup$ @The number of edges is 27. $\endgroup$ – svsring May 15 '16 at 11:31
  • $\begingroup$ Ha, forgot the overcount :P. $\endgroup$ – Henry Lee May 15 '16 at 18:33
5
$\begingroup$

Hint: It is a lot easier to count their complements.

$\endgroup$
  • $\begingroup$ I assume the complement is a 2-regular graph on 9 vertices correct? $\endgroup$ – Henry Lee May 15 '16 at 2:04
  • $\begingroup$ @HenryLee: Correct, $\endgroup$ – hmakholm left over Monica May 15 '16 at 2:43
  • $\begingroup$ That would mean there's only one graph though...is it only one? $\endgroup$ – Henry Lee May 15 '16 at 3:02
  • $\begingroup$ @HenryLee: No, there are four. (Are you perhaps imagining that the complement has to be connected?) $\endgroup$ – hmakholm left over Monica May 15 '16 at 7:46
  • $\begingroup$ Wouldn't it have to because it's 2-regular? $\endgroup$ – Henry Lee May 15 '16 at 18:33
0
$\begingroup$

They can be generated using geng which is packaged with Nauty using the command ./geng 9 -d6 -D6. Feeding this into showg will show the adjacencies of the graphs, which we draw as follows:

the non-isomorphic 6-regular graphs on 9 vertices

We color the non-edges red and identify the complement graphs below each graph. We can readily see why it's easier to count the 2-regular graphs and take their complements.

Since isomorphims map edges to edges, and non-edges to non-edges, two graphs are isomorphic if and only if their complements are isomorphic.

$\endgroup$

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.