On the edge-integrity of some graphs and their complements (Q1313866)

The edge integrity of a graph \(G\) is defined as \(I'(G)=\min_{S \subseteq E(G)} \{| S |+m (G-S)\}\) where \(m(G-S)\) denotes the order of a largest component of \(G-S\). A graph \(G\) is called honest if \(I'(G)=p\) where \(p\) is the order of \(G\). Some Nordhaus-Gaddum type results are obtained after which the authors ask when \(I'(G) + I' (\overline G) = 2p\). After asking for which graphs \(G\) do both \(G\) and its complement have diameter 2, the authors study graphs with diameter 2. They then show (Theorem 8), for example, that if graphs \(G\) and \(H\) each have order at least 3 then \(\overline {G \times H}\) is honest. One of the closing questions asks for the edge integrity of self-complementary graphs.