4
$\begingroup$

This is Trudeau's exercise 2.16:

Find a self-complementary graph with $v = 8$. Of the $12, 346$ graphs with $v = 8$ only four are self-complementary.

The picture in below is the answer that the book itself provides: enter image description here

And the picture in below is the answer that I have found: enter image description here

Given that the book says there are only four graphs that are self-complementary with $v = 8$ did I discover two new ones or my graphs are somehow isomorphic to those provided by the book?

Note: My graphs are drawn with their complements in one figure hence the different colors.

If my graphs are isomorphic to those provided by the book, could you please provide the labels of vertices that make them isomorphic? Where is my mistake?

Thank you in advance.

$\endgroup$
4
$\begingroup$

The graph on the left is Fanny. You will find the isomorphisms by matching the vertices of degree 2.

The graph on the right isn't any of the four.

Note that OEIS says there are 10 self-complementary graphs on 8 vertices https://oeis.org/A000171. They are shown in http://mathworld.wolfram.com/Self-ComplementaryGraph.html In fact your graph from the right picture appears there as "8-self-complementary graph 3".

$\endgroup$
2
$\begingroup$

To complement Michal's answer, you can see that your left graph is Fanny Zambuto by keeping the edge relations you have, but by permuting the locations $A \mapsto C \mapsto E \mapsto G \mapsto A$.

$\endgroup$
  • 1
    $\begingroup$ And we can see that the right graph isn't any of the four because its degree sequence $2,2,2,2,5,5,5,5$ doesn't match any of the examples except Fanny Zambuto, but (unlike Fanny) its degree-$2$ vertices come in pairs which have the same degree-$5$ neighbors. $\endgroup$ – Misha Lavrov Aug 22 '18 at 16:47

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.