zbMATH — the first resource for mathematics

A note on the independent domination number versus the domination number in bipartite graphs. (English) Zbl 1458.05208
Summary: 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 and L. Volkmann [Discrete Appl. Math. 161, No. 18, 3087–3089 (2013; Zbl 1287.05107)]). 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.

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C05 Trees
Zbl 1287.05107
Full Text: DOI arXiv