About triangles in a graph and its complement (Q1332419)

The authors consider finite, undirected graphs \(G\) with no loops and multiple edges. The symbols \(\overline G\), \(N(u)\), \(N[u]= \{u\}\cup N(u)\), \(d(u)\), \(\overline d(u)\), \(t(u)\), \(\overline t(u)\), \(t(G)\) and \(G(S)\), respectively denote the complement of \(G\), (open) neighbourhood of the vertex \(u\) in \(G\), closed neighbourhood of \(u\) in \(G\), degree of \(u\) in \(G\), degree of \(u\) in \(\overline G\), number of triangles in \(G\) containing \(u\), number of triangles in \(\overline G\) containing \(u\), total number of triangles in \(G\) and the subgraph of \(G\) induced by \(S\subseteq V(G)\). Define a graph \(G\) to be self-complementary if \(G\) and \(\overline G\) are isomorphic. It is known that every self-complementary graph is connected with diameter 2 or 3 and of order \(4k\) or \(4k+1\) for some natural number \(k\). If it is regular also, then diameter is 2, order is \(4k+1\), and regularity is \(2k\). For a self-complementary graph \(G\), there exist isomorphisms \(\sigma: G\to \overline G\) under which \(G\) and \(\overline G\) are isomorphic. Such isomorphisms are called complementing permutations and the collection of all complementing permutations \(\sigma: G\to\overline G\) is denoted by \({\mathcal C}(G)\). Finally, a vertex \(u\) in a self-complementary graph \(G\) is called fixed point if \(\sigma(u)= u\) for some \(\sigma\in {\mathcal C}(G)\). (i) Ringel (1963) and Sachs (1962) have both proved that a self- complementary graph \(G\) of order \(p\) has no fixed point if \(p\) is even and has exactly one fixed point associated with each \(\sigma\in {\mathcal C}(G)\) if \(p\) is odd. (ii) Rao (1985) defined the set \(F(G)= \{u\in V(G): \sigma(u)= u\) for some \(\sigma\in {\mathcal C}(G)\}\) for a self-complementary graph \(G\) and the set \(\widehat F(G)=\{u\in V(G): t(u)= k(k-1)\}\) for a regular self- complementary graph \(G\) of order \(p= 4k+1\) and proved that \(F(G)\subseteq \widehat F(G)\) if \(G\) is regular self-complementary and \(F(G)= V(G)\) if and only if \(G\) is vertex-symmetric self-complementary. (iii) Goodman (1959) estimated the minimum value of \(t(G)+ t(\overline G)\) for a graph \(G\) and Lordon (1962) derived the exact value. Clapham (1973) deduced the minimum value of \(t(G)\) for a self-complementary graph \(G\) and the exact value for a regular self-complementary graph. (iv) In the present paper the author derive the value \(t(u)+ \overline t(u)\) for any vertex \(u\) in a graph \(G\) and deduce Lordon's estimate of \(t(G)+ t(\overline G)\) for any graph \(G\), Clapham's estimate of \(t(G)\) for any regular self-complementary graph \(G\) and the result \(F(G)\subseteq \widehat F(G)\) by Rao. Also, a characterization of \(\widehat F(G)\) is obtained, which provides a motivation to extend its definition to any graph \(G\). Finally a discussion of a conjecture by Kotzig (1979) that \(F(G)= \widehat F(G)\) for regular self-complementary graphs is presented.