A note on the independent domination number versus the domination number in bipartite graphs

Czechoslovak Mathematical Journal

Shaohui Wang, Bing Wei¹ 

关键词: domination;    independent domination;   

DOI  :  10.21136/CMJ.2017.0068-16

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

  Let $\gamma(G)$ and $i(G)$ be the domination number and the independent domination number of $G$, respectively. Rad and Volkmann posted a conjecture that $i(G)/ \gamma(G) \leq\Delta(G)/2$ for any graph $G$, where $\Delta(G)$ is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than $\Delta(G)/2$ are provided as well.

【 授权许可】

Unknown