Independent domination of graphs with bounded maximum degree.

An independent dominating set of a graph, also known as a maximal independent set, is a set S of pairwise non-adjacent vertices such that every vertex not in S is adjacent to some vertex in S. We prove that for Δ = 4 or Δ ≥ 6 , every connected n -vertex graph of maximum degree at most Δ has an independent dominating set of size at most (1 − Δ ⌊ Δ 2 / 4 ⌋ + Δ) (n − 1) + 1. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most (1 − Δ ⌊ Δ 2 / 4 ⌋ + Δ) n. [ABSTRACT FROM AUTHOR]