On the Nordhaus-Gaddum problem for the edge cost of a graph (Q2721334)

Let \(G\) be a graph on \(n\) nodes. Let \(G^+\) be a graph obtained from \(G\) by adding a node \(w\) and some extra edges. The system \(G^+\) is node fault tolerant if after removing any node from \(G^+\) the resulting graph contains a graph isomorphic to \(G\). The edge cost of \(G\), denoted by \(\text{ec}(G)\), is the minimum number of extra edges that must be added in \(G^+\) in order to ensure node fault tolerance. The author obtains bounds for the sum and product of the edge cost of a graph and its complement, analogous to the theorem of Nordhaus and Gaddum. In particular, the author shows that for a graph \(G\) of order \(n\), \(n\leq \text{ec}(G)+ \text{ec}(\overline G)\leq 2n\) and \(0\leq \text{ec}(G)\cdot \text{ec}(\overline G)\leq n^2\).