Hadwiger numbers of self-complementary graphs

Abstract

The Hadwiger number of a graph $G$, denoted by $h(G)$, is the order of the largest complete minor of $G$. A graph is said to be self-complementary if it is isomorphic to its complement. We prove that for all $n\equiv 0,1(\text{mod 4})$ and for all $\lfloor \frac{n+1}{2}\rfloor \le h\le \lfloor \frac{3n}{5}\rfloor$, there exists a self-complementary graph $G$ with $n$ vertices whose Hadwiger number is $h$.

6 pages, 4 figures, 1 table