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, \v Skrekovski, 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.
|
