Search

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.

Let αo(G) denote the point coverning number of a graph G, let βo(G) denote the point independence number of G. In 1959, Gallai [1] proved that, for any graph G having p points, αo(G)+βo(G)=p. This paper contains several generalizations of Gallai's Theorem of the form αo(P)+βo(P)=p, where αo(P) and βo(P) denote generalizations of αo(G) and βo(G) to a broad class of properties P which are called hereditary. A property P of a graph G is hereditary if, whenever G has property P and G′ is a subgraph of G, then G′ also has property P.

We shall derive a formula for the expected value μ(n) of the node-independence number of a random tree with n labelled nodes and we shall determine the asymptotic behaviour of μ(n) as n tends to infinity.