BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20211207T163000
DTEND;TZID=Asia/Seoul:20211207T173000
DTSTAMP:20260424T031039
CREATED:20211207T073000Z
LAST-MODIFIED:20240707T080616Z
UID:4804-1638894600-1638898200@dimag.ibs.re.kr
SUMMARY:Eun-Kyung Cho (조은경)\, Independent domination of graphs with bounded maximum degree
DESCRIPTION: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. \nLet $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. \nLet $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. \nIn 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’$. \nMoreover\, 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. \nThis talk is based on joint work with Ilkyoo Choi\, Hyemin Kwon\, and Boram Park.
URL:https://dimag.ibs.re.kr/event/2021-12-07/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR