The connectivity of a graph and its complement
Let G G be a graph with minimum degree ?(G) ? ( G ) , edge-connectivity ?(G) ? ( G ) , vertex-connectivity ?(G) ? ( G ) , and let G ? be the complement of G G . In this article we prove that either ?(G)=?(G) ? ( G ) = ? ( G ) or ? ( G ? ) = ? ( G ? ) . In addition, we present the NordhausGaddum type result ? ( G ) + ? ( G ? ) ? min { ? ( G ) , ? ( G ? ) } + 1 . A family of examples will show that this inequality is best possible.
edge-connectivity vertex-connectivity nordhausgaddum type results complementary graph