What are other graphs of order $n$ than the star $K_{1, n-1}$ which are not packable?

19 Views Asked by At

We say, that a graph $G$ is packable, if it is isomorphic to a subgraph of its complement.

In more formal terms:

A graph $G$ is packable, if there is a permutation $\sigma : V(G) \to V(G)$ such that

$$\forall_{u,v \in V(G)} \quad : \quad uv \in E(G) \quad \Rightarrow \quad \sigma(u)\sigma(v) \notin E(G)$$

Except the obvious example $K_{1, n-1}$, which is not packable, what other graphs of order $n$ are not packable?

The hint we got from our Professor is we should find "a graph where a star would be a subgraph of it", and that it should be rather "small examples".