• This event has passed.

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

## Tuesday, December 7, 2021 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

### Speaker

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.

## Details

Date:
Tuesday, December 7, 2021
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Room B232
IBS (기초과학연구원)

## Organizer

Sang-il Oum (엄상일)
View Organizer Website
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209