On separable self-complementary graphs (Q1850001)

The authors consider simple finite undirected graphs. Their first result is a set of necessary and sufficient conditions for the complement \(\overline G\) of a separable graph \(G\) to be separable or disconnected. If \(H\) is a graph and \(P_4=v_1v_2v_3v_4\) is a 4-path, then the graph \(G\) obtained from \(H\cup P_4\) by joining \(v_2\) and \(v_3\) to every vertex of \(H\) is said to be obtained from \(H\) by a 4-path addition. The authors' second result is that every separable self-complementary graph with at least 4 vertices is obtained from a graph \(H\) by a 4-path addition, where \(H\) is either empty, trivial or self-complementary. Using this result and the known enumeration of self-complementary graphs, the authors are able to enumerate all separable self-complementary graphs, by proving that the number of separable self-complementary graphs with \(n\geq 8\) vertices is the same as the number of self-complementary graphs with \(n-4\) vertices.