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^{\prime }$ be a connected $k$-regular graph that is not $K_{k,k}$ where $k\ge 3$. We prove that $i(G^{\prime })\le \frac{k-1}{2k-1}|V(G^{\prime })|$, 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^{\prime })}{\gamma (G^{\prime })}\le \frac{k^3-3k^2+2}{2k^2-6k+2}$, strengthening upon a result of Knor, Škrekovski, and Tepeh, where $\gamma (G^{\prime })$ is the domination number of $G^{\prime }$.

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

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