On the Nordhaus-Gaddum class problems.
Nirmala Achuthan, N. R. Achuthan, Lou Caccetta · 1990
Abstract: Let!:ten) denote the class of simple graphs of order n. For G €!:t(n) , G denotes the complement of G. Given a graph theoretic parameter f, the Nordhaus-Gaddum Problem is to find lower and upper bounds for: and f(G) + f(G), f(G) f(G), over the class!:ten). In this paper we consider a variation of this problem by restricting our attention to the subclass of!:ten) consisting of graphs having exactly m edges. We consider the parameters edge connectivity, diameter and chromatic number. We also consider the problem of characterizing the extremal graphs and the realizability problem. 1.