On regular and strongly-regular self-complementary graphs (Q2266719): Difference between revisions

A graph G is called self-complementary, if it is isomorphic to its own complement. The symbol \({\mathcal C}(G)\) denotes the set of permutations of the vertex set V(G) of G which induce isomorphisms of G onto its complement. Further F(G) is the set of all vertices u of G for which there exists \(\sigma\in {\mathcal C}(G)\) such that \(\sigma (u)=u\); N(G) is the set of all edges \(\{\) u,v\(\}\) of G for which there exists \(\sigma\in {\mathcal C}(G)\) such that \(\sigma (u)=v\). The symbol \(\hat F(\)G) denotes the set of all vertices of G which belong to exactly k(k-1) triangles of G, where k is such a number that \(n=4k\) or \(n=4k+1\), where \(n=| V(G)|\). A. Kotzig has proposed the following problems: A. Characterize the subset F(G) of a regular self-complementary graph G. Is it true that \(F(G)=\hat F(G)\) for a regular self-complementary graph G? B. Characterize the set N(G) for a self-complementary graph G. C. Is it true that a regular self-complementary graph G is strongly regular if and only if \(F(G)=V(G)\) and \(N(G)=E(G)?\) In the paper these problems are solved.