Nordhaus-Gaddum results for CO-irredundance in graphs (Q1969790)

The subgraph of a graph \(G\) induced by a subset \(S\) of the vertex set \(V\) is denoted by \(G[S]\). The open neighbourhood of a vertex \(t\), i.e., the set of all vertices of \(G\) adjacent to \(t\), is denoted by \(N(t)\). Let \(S\subseteq V\) and \(s\in S\). A vertex \(t\) is an \(S\)-private neighbour of \(s\), if either \(t= s\) and \(s\) is isolated in \(G[S]\), or \(t\in V-S\) and \(N(t)\cap S= \{s\}\), or \(t\in S\) and \(N(t)\cap S= \{s\}\). If each vertex of \(S\) has an \(S\)-private neighbour, \(S\) is called CO-irredundant. The maximum number of vertices of a CO-irredundant set in \(G\) is the CO-irredundance number \(\text{COIR}(G)\) of \(G\). Results of Nordhaus-Gaddum type for \(G\) and its complement \(\overline G\) are stated: \(\text{COIR}(G)+ \text{COIR}(\overline G)\leq n+2\) and \(\text{COIR}(G)\cdot \text{COIR}(\overline G)\leq \lfloor(n+ 2)^2/4\rfloor\); where \(n\) is the number of vertices of \(G\).