Article ID Journal Published Year Pages File Type
419841 Discrete Applied Mathematics 2008 4 Pages PDF
Abstract

Let GG be a graph with minimum degree δ(G)δ(G), edge-connectivity λ(G)λ(G), vertex-connectivity κ(G)κ(G), and let Ḡ be the complement of GG.In this article we prove that either λ(G)=δ(G)λ(G)=δ(G) or λ(Ḡ)=δ(Ḡ). In addition, we present the Nordhaus–Gaddum type result κ(G)+κ(Ḡ)≥min{δ(G),δ(Ḡ)}+1. A family of examples will show that this inequality is best possible.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
The connectivity of a graph and its complement
Authors
, ,