Average lower independence in trees and outerplanar graphs

Research output: Contribution to journalArticlepeer-review


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 iav(G) = 1/|V| ∑v∈V iv(G). In this paper, we show that if G is a tree of order n, then iav(G) ≥ 2√n + 0(1), while if G is an outer-planar graph of order n, then i av(G) ≥ 2√n/3 + 0(1). Both bounds are asymptotically sharp.

Original languageEnglish
Pages (from-to)147-159
Number of pages13
JournalArs Combinatoria
Publication statusPublished - Oct 2003
Externally publishedYes


  • Average lower independence
  • Outerplanar graphs
  • Trees

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'Average lower independence in trees and outerplanar graphs'. Together they form a unique fingerprint.

Cite this