Wednesday, June 1 2022

4:00pm - 5:15pm

4:00pm - 5:15pm

Department Seminar

Department Seminar: Independent domination number of regular graphs, Ilkyoo Choi, Hankuk University of Foreign Studies, Republic of

Korea

Korea

Title: Independent domination number of regular graphs

Speaker: Ilkyoo Choi, Hankuk University of Foreign Studies, Republic of

Korea

The speaker will be remote on zoom.

Contact mathstats-staff@ucdenver.edu for Zoom info

Abstract: The independent domination number of a graph $G$, denoted $i(G)$, is the minimum size of an independent dominating set of $G$. We recently proved a series of results regarding independent domination of regular graphs. One result is the following: Let $G$ be a connected $r$-regular graph that is not $K_{r,r}$ where $r\geq 3$. We prove that $i(G)\leq \frac{r-1}{2r-1}|V(G)|$, which is tight for $r\in\{3,4\}$, generalizing a result by Lam, Shiu, and Sun. This result also answers a question by Goddard et al. in the affirmative. Moreover, if we restrict $G$ to be a $3$-regular graph without $4$-cycles, then we prove that $i(G)\leq \frac{4}{11}|V(G)|$, which improves a result by Abrishami and Henning. We also investigate independent domination for the class of graphs with bounded maximum degree. This talk is based on joint work with Eun-Kyung Cho, Hyemin Kwon, and Boram Park.

Speaker: Ilkyoo Choi, Hankuk University of Foreign Studies, Republic of

Korea

The speaker will be remote on zoom.

Contact mathstats-staff@ucdenver.edu for Zoom info

Abstract: The independent domination number of a graph $G$, denoted $i(G)$, is the minimum size of an independent dominating set of $G$. We recently proved a series of results regarding independent domination of regular graphs. One result is the following: Let $G$ be a connected $r$-regular graph that is not $K_{r,r}$ where $r\geq 3$. We prove that $i(G)\leq \frac{r-1}{2r-1}|V(G)|$, which is tight for $r\in\{3,4\}$, generalizing a result by Lam, Shiu, and Sun. This result also answers a question by Goddard et al. in the affirmative. Moreover, if we restrict $G$ to be a $3$-regular graph without $4$-cycles, then we prove that $i(G)\leq \frac{4}{11}|V(G)|$, which improves a result by Abrishami and Henning. We also investigate independent domination for the class of graphs with bounded maximum degree. This talk is based on joint work with Eun-Kyung Cho, Hyemin Kwon, and Boram Park.

Speaker: | Ilkyoo Choi |

Affiliation: | Hankuk University of Foreign Studies, Republic of Korea |

Location: | ( virtual on zoom ) |

Done