Eun-Kyung Cho (조은경), Independent domination of graphs with bounded maximum degree

The independent domination number of a graph $G$, denoted $i(G)$, is the minimum size of an independent dominating set of $G$. In this talk, we prove a series of results regarding independent domination of graphs with bounded maximum degree.

Let $G$ be a graph with maximum degree at most $k$ where $k \ge 1$. We prove that if $k = 4$, then $i(G) \le \frac{5}{9}|V(G)|$, which is tight. Generalizing this result and a result by Akbari et al., we suggest a conjecture on the upper bound of $i(G)$ for $k \ge 1$, which is tight if true.

Let $G’$ be a connected $k$-regular graph that is not $K_{k, k}$ where $k\geq 3$. We prove that $i(G’)\le \frac{k-1}{2k-1}|V(G’)|$, which is tight for $k \in \{3, 4\}$, generalizing a result by Lam, Shiu, and Sun. This result also answers a question by Goddard et al. in the affirmative.

In addition, we show that $\frac{i(G’)}{\gamma(G’)} \le \frac{k^3-3k^2+2}{2k^2-6k+2}$, strengthening upon a result of Knor, Škrekovski, and Tepeh, where $\gamma(G’)$ is the domination number of $G’$.

Moreover, if we restrict $G’$ to be a cubic graph without $4$-cycles, then we prove that $i(G’) \le \frac{4}{11}|V(G’)|$, which improves a result by Abrishami and Henning.

This talk is based on joint work with Ilkyoo Choi, Hyemin Kwon, and Boram Park.