4
$\begingroup$

Given a graph, is there any algorithm to build from it a self-complementary graph, by adding edges and vertices? I'm also interested in minimizing the number of added nodes.

Thank you!

$\endgroup$
0

1 Answer 1

6
$\begingroup$

Say you have a graph $G$, with complement $G^c$. Create a new graph: $$G \equiv G^c \equiv G^c \equiv G$$ where $H_1 \equiv H_2$ means that every vertex in $H_1$ is connected to every vertex in $H_2$. Then this graph is self complementary (why?) and since it contains a copy of $G$, it can be built up from $G$.

$\endgroup$
2
  • $\begingroup$ this is a good theoretical answer, but I imagine an algorithm based on this would not be efficient $\endgroup$
    – Bogdan B
    Dec 11, 2017 at 19:32
  • $\begingroup$ Yes, that's a good answer. However, I'm interested in minimizing the number of added nodes. Is there any other method (including the probabilistic ones, if there are any) to build such a graph? $\endgroup$
    – saa
    Dec 11, 2017 at 19:46

You must log in to answer this question.

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