2
$\begingroup$

Recently, a user asked for the construction of regular self-complementary graphs.

I found the graph consisting of the hamilton-circles

$$1-5-8-3-9-6-2-4-7-1$$ and $$1-3-5-2-9-4-8-7-6-1$$ with $9$ vertices and $18$ edges,but it is not planar.

I searched some more graphs with $9$ vertices and $18$ edges, which are both $4$-regular and self-complementary, but none of them was planar.

So my question :

  • Is there a $4$-regular planar self-complementary graph with $9$ vertices and $18$ edges ?
$\endgroup$

2 Answers 2

3
$\begingroup$

According to my calculations in sage, there are 16 4-regular graphs on 9 vertices, of which only one is planar. The planar graph is the line graph of the complement of $C_6$, and it is not self-complementary.

$\endgroup$
1
$\begingroup$

Battle, Harary, and Kodama [Bull. Amer. Math. Soc. 68 (1962), 569–571; MR0155314], and others have shown that every planar graph with nine vertices has a non-planar complement. See also Battle, Joseph; Harary, Frank; Kodama, Yukihiro [Bull. Amer. Math. Soc. 68 1962 569–571;MR0155314].

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .