The connectivity of a graph and its complement |
| |
| Authors: | Angelika Hellwig |
| |
| Institution: | a Institut für Medizinische Statistik, Universitätsklinikum der RWTH Aachen, Pauwelsstraße 30, 52075 Aachen, Germany
b Lehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, Germany |
| |
| Abstract: | Let G be a graph with minimum degree δ(G), edge-connectivity λ(G), vertex-connectivity κ(G), and let  be the complement of G.In this article we prove that either λ(G)=δ(G) or  . In addition, we present the Nordhaus-Gaddum type result  . A family of examples will show that this inequality is best possible. |
| |
| Keywords: | Edge-connectivity Vertex-connectivity Complementary graph Nordhaus-Gaddum type results |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
