Bounds for the Independent Domination Number of Graphs and Planar Graphs

摘要

We first prove that if G is a connected graph with n vertices and chromatic number x(G) = k ≥ 2, then its independent domination number i(G) ≤ [ ((k-1)/k)n]-(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 [n/3].