ON THE INDEPENDENCE NUMBERS OF COMPLEMENTARY GRAPHS

Abstract

A bstract A 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.