Question

On the independence numbers of complementary graphs

Answer 1

AbstractA set of vertices (edges) is called independent if no two vertices (edges) in the set are adjacent. The independence number β(G) (edge independence number β1(G)) is the maximum number of elements in an independent set of vertices (edges) of G. It is shown for any graph G of order p ≥ 3, having complement Ḡ, that [p/2] ≤ β1(G) + β1(Ḡ) ≤ 2[p/2]. From this, upper and lower bounds for β1(G) · β1(Ḡ) are determined. All four bounds are shown to be best possible. It is verified that for every graph G of order p, the bounds β(G) + β(Ḡ) ≤ p + 1 and β(G) · β(Ḡ) ≤ [(p + 1)/2] · {(p + 1)/2} hold and are best possible. Lower bounds for β(G) + β(Ḡ) and β(G) · β(Ḡ) are considered and are shown to be related to Ramsey numbers.Citing Literature

Volume36, Issue3 Series II

March 1974

Pages 247-251