Average Lower Independence in Trees and Outerplanar Graphs

Abstract

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) = \frac{1}{|V|} \sum_{v\in V} i_v(G)\). In this paper, we show that if \(G\) is a tree of order \(n\), then \(i_{av}(G) \geq {2}\sqrt{n} + O(1)\), while if \(G\) is an outer-planar graph of order \(n\), then \(i_{av}(G) \geq 2\sqrt{\frac{n}{3}} + O(1)\). Both bounds are asymptotically sharp.