Jinha Kim (김진하), 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 $\mathrm{\Delta }=4$ or $\mathrm{\Delta }\ge 6$, every connected $n$-vertex graph of maximum degree at most $\mathrm{\Delta }$ has an independent dominating set of size at most $(1-\frac{\mathrm{\Delta }}{\lfloor {\mathrm{\Delta }}^2/4\rfloor +\mathrm{\Delta }})(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-\frac{\mathrm{\Delta }}{\lfloor {\mathrm{\Delta }}^2/4\rfloor +\mathrm{\Delta }})n$.
This is joint work with Eun-Kyung Cho, Minki Kim, and Sang-il Oum.