0
$\begingroup$

I'm trying to construct the collection of self-complementary graphs which are also bipartite. For a graph G to be self-complementary, then its complement must be isomorphic to G. If G is bipartite and self-complementary, then I believe that it's complement must also be bipartite. But I'm wondering if the complement is necessarily bipartite on the same subsets of vertices? In other words, if I have a self-complementary bipartite graph G with bipartition (X,Y) where X and Y are subsets of V(G), then is the complement of G also bipartite on (X,Y)? Or can it be bipartite on two different subsets of vertices? In that case, could you still say that the two graphs are isomorphic?

$\endgroup$
1
  • $\begingroup$ The vertex sets don't have to be identical. There has to be a one-to-one correspondence that preserves adjacency. Look at the definition of isomorphism again. $\endgroup$ – saulspatz Sep 29 '19 at 15:39
0
$\begingroup$

HINT: If both a graph $G$ and its complement are bipartite, then it can have no more than 4 vertices. Indeed, if $G$ is bipartite and has 5 or more vertices, which implies that one side $S$ of $G$ has at least 3 vertices, which implies that the complement of $G$ contains a complete graph on $S$ and thus has a triangle [as $|S| \ge 3$] and is not bipartite.

So now you are left considering graphs on 4 or fewer vertices, which is quite a small enough search space.

$\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.