Claw-free Steinhaus Complements

Steinhaus graphs are a small (there are \( 2^{n-1} \) of them on \( n \) vertices) but interesting family of graphs. They have been studied for over forty years, and it has been shown that almost all graphs have certain properties if and only if almost all Steinhaus graphs have these properties.

In this paper, we find and count all the complements of Steinhaus graphs that are claw-free.