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

Abstract

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.