Search

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.