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’$ 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.

Eun-Kyung Cho (조은경) gave a talk on the problem of decomposing a graph into a d-degenerate graph and a graph of bounded maximum degree at the Discrete Math Seminar

On March 3, 2020, Eun-Kyung Cho (조은경) from Hankuk University of Foreign Studies presented a talk on the existence of a decomposition of a planar graph into two edge-disjoint subgraphs, one of which is d-degenerate and the other has maximum degree at most h at the discrete math seminar. The title of her talk was “Decomposition of a planar graph into a d-degenerate graph and a graph with maximum degree at most h“. She will visit the IBS discrete math group until March 6.

Eun-Kyung Cho (조은경), Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$

Given a graph $G$, a decomposition of $G$ is a collection of spanning subgraphs $H_1, \ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i \in \{1, \ldots, t\}$. Given a positive integer $d$, a graph is said to be $d$-degenerate if every subgraph of it has a vertex of degree at most $d$. Given a non-negative integer $h$, we say that a graph $G$ is $(d,h)$-decomposable if there is a decomposition of $G$ into two spanning subgraphs, where one is a $d$-degenerate graph, and the other is a graph with maximum degree at most $h$.

It is known that a planar graph is $5$-degenerate, but not always $4$-degenerate. This implies that a planar graph is $(5,0)$-decomposable, but not always $(4,0)$-decomposable. Moreover, by related previous results, it is known that a planar graph is $(3,4)$- and $(2,8)$-decomposable.

In this talk, we improve these results by showing that every planar graph is $(4,1)$-, $(3,2)$-, and $(2,6)$-decomposable. The $(4,1)$- and $(3,2)$-decomposabilities are sharp in the sense that the maximum degree condition cannot be reduced more.

This is joint work with Ilkyoo Choi, Ringi Kim, Boram Park, Tingting Shan, and Xuding Zhu.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright © IBS 2018. All rights reserved.