On the Nordhaus-Gaddum Problem for the Edge Cost of a Graph

Let \(G\) be a simple graph with \(n\) vertices, and let \(\overline{G}\) denote the complement of \(G\). A well-known theorem of Nordhaus and Gaddum [6] bounds the sum \(\chi(G) + \chi(\overline{G})\) and product \(\chi(G)\chi(\overline{G})\) of the chromatic numbers of \(G\) and its complement in terms of \(n\). The \emph{edge cost} \(ec(G)\) of a graph \(G\) is a parameter connected with node fault tolerance studies in computer science. Here we obtain bounds for the sum and product of the edge cost of a graph and its complement, analogous to the theorem of Nordhaus and Gaddum.