Average lower independence in trees and outerplanar graphs

For a vertex v of a graph G = (V, E), the lower independence number i(v)(G) of G relative to v is the minimum cardinality of a maximal independent set in G that contains v. The average lower independence number of G is i(av)(G) = 1/\V\ Sigma(vis an element ofV) i(v)(G). In this paper, we show that if G is a tree of order n, then i(av)(G) greater than or equal to 2rootn + O(1), while if G is an outer-planar graph of order n, then i(av)(G) 2rootn-/3 + O(1). Both bounds are asymptotically sharp.