Independent domination of graphs with bounded maximum degree

Abstract

© 2022 Elsevier Inc.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 [Formula presented]. 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 [Formula presented].