Bounds for the Independent Domination Number of Graphs and Planar Graphs

Abstract

We first prove that if $G$ is a connected graph with $n$ vertices and chromatic number $\chi (G)=k\ge 2$, then its independent domination number

$$i(G)\le \lceil \frac{(k-1)}{k}n\rceil –(k-2).$$

This bound is tight and remains so for planar graphs. We then prove that the independent domination number of a diameter two planar graph on $n$ vertices is at most $\lceil \frac{n}{3}\rceil$.