A self-complementary graph from a given degree sequence

Question

Consider a degree sequence of a graph with 8 vertices such as (1,2,3,3,4,4,5,6). It is straightforward to prove that this is a graphic degree sequence and, indeed, I have created at least half a dozen possibilities at random. On the face of it, based on the fact that subtracting each element of the degree sequence from 7 creates the same degree sequence, it seems that one of the simply connected graphs created from it should be self-complementary. Here's the two part question:

1) Is there any way to confirm the existence of a self-complementary simply connected graph from such a degree sequence? 2) Is there any simple algorithm for constructing it from such a sequence?

Answer 1

You can see there can't be one in this case. Either there is an edge between the nodes of valence $1$ and $6$, in which case there isn't in the complement, or there is no edge between the nodes of valence $1$ and $6$, but there is in the complement.

If $a_1\leq a_2\leq\cdots\leq a_n$ are the valences you want, define for each $a,$ the value $k_a=\left\{i\mid a_i=a\right\}$. You then need:

1. $a_i+a_{n+1-i}=n-1$ for all $i=1,\dots,n.$
2. $n\equiv 0,1\pmod 4$ since otherwise $\binom{n}{2}$ is odd, and thus the complement of a graph has a different number of edges as the graph.
3. If $a\neq (n-1)/2$ then $k_a$ must be even. Otherwise, if we take the bipartite subgraph of edges from the $k_a$ nodes of valence $a$ to the $k_a$ nodes of valence $n-1-a$, it would have to be half of the complete bipartite graph edges, which has $k_a^2$ elements. If $k_a$ is odd, then $k_a^2$ is odd, so this is not possible. (This is a generalization for your initial case.)
4. If $n$ is odd, then $k_{(n-1)/2}\equiv 1\pmod{4}$. Taking the subgraph of nodes of valence $(n-1)/2$, it must be self-complementary, and thus $\binom{k_{(n-1)/2}}{2}$ must be even. This means you need $k_{(n-1)/2}\equiv 0,1\pmod 4$. But if $n$ is odd, then you need $k_{(n-1)/2}$ odd, by the symmetry of $a_1\leq a_2\leq\cdots \leq a_n.$ So you need $k_{(n-1)/2}\equiv 1\pmod{4}$.

I still don't have a sufficient condition.