The connectivity of a graph and its complement
The connectivity of a graph and its complement
复制标题
DOI：
10.1016/j.dam.2008.05.012
复制
发表时间：
2008-10
期刊：
影响因子：
--
通讯作者：
Angelika Hellwig;L. Volkmann
中科院分区：
文献类型：
--
作者：
Angelika Hellwig;L. Volkmann
设G是最小度δ（G），边连通度λ（G），点连通度κ（G）的图，G的补图为G的补图.本文证明了λ（G）=δ（G）或λ（G <$）=δ（G <$）.此外，我们还得到了Nordhaus-Gaddum型结果κ（G）+κ（G <$）≥min{δ（G），δ（G <$）}+1.一组例子将表明，这种不等式是最好的可能。
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 κ(G)+κ(Ḡ)≥min{δ(G),δ(Ḡ)}+1. A family of examples will show that this inequality is best possible.