Geodesic
A note on the independent domination number versus the domination number in bipartite graphs
Czechoslovak Mathematical Journal, Tome 67 (2017) no. 2, pp. 533-536 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2017.0068-16
Classification : 05C05, 05C69
Keywords: domination; independent domination 
@article{10_21136_CMJ_2017_0068_16,
     author = {Wang, Shaohui and Wei, Bing},
     title = {A note on the independent domination number versus the domination number in bipartite graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {533--536},
     year = {2017},
     volume = {67},
     number = {2},
     doi = {10.21136/CMJ.2017.0068-16},
     mrnumber = {3661058},
     zbl = {06738536},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0068-16/}
}
TY  - JOUR
AU  - Wang, Shaohui
AU  - Wei, Bing
TI  - A note on the independent domination number versus the domination number in bipartite graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2017
SP  - 533
EP  - 536
VL  - 67
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0068-16/
DO  - 10.21136/CMJ.2017.0068-16
LA  - en
ID  - 10_21136_CMJ_2017_0068_16
ER  - 
%0 Journal Article
%A Wang, Shaohui
%A Wei, Bing
%T A note on the independent domination number versus the domination number in bipartite graphs
%J Czechoslovak Mathematical Journal
%D 2017
%P 533-536
%V 67
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2017.0068-16/
%R 10.21136/CMJ.2017.0068-16
%G en
%F 10_21136_CMJ_2017_0068_16
Wang, Shaohui; Wei, Bing. A note on the independent domination number versus the domination number in bipartite graphs. Czechoslovak Mathematical Journal, Tome 67 (2017) no. 2, pp. 533-536. doi: 10.21136/CMJ.2017.0068-16

[1] Allan, R. B., Laskar, R.: On domination and independent domination numbers of a graph. Discrete Math. 23 (1978), 73-76. | DOI | MR | JFM

[2] Beyer, T., Proskurowski, A., Hedetniemi, S., Mitchell, S.: Independent domination in trees. Proc. Conf. on Combinatorics, Graph Theory and Computing Baton Rouge, 1977, Congressus Numerantium, Utilitas Math., Winnipeg (1977), 321-328. | MR | JFM

[3] Furuya, M., Ozeki, K., Sasaki, A.: On the ratio of the domination number and the independent domination number in graphs. Discrete Appl. Math. 178 (2014), 157-159. | DOI | MR | JFM

[4] Goddard, W., Henning, M. A.: Independent domination in graphs: A survey and recent results. Discrete Math. 313 (2013), 839-854. | DOI | MR | JFM

[5] Goddard, W., Henning, M. A., Lyle, J., Southey, J.: On the independent domination number of regular graphs. Ann. Comb. 16 (2012), 719-732. | DOI | MR | JFM

[6] Rad, N. J., Volkmann, L.: A note on the independent domination number in graphs. Discrete Appl. Math. 161 (2013), 3087-3089. | DOI | MR | JFM

[7] Southey, J., Henning, M. A.: Domination versus independent domination in cubic graphs. Discrete Math. 313 (2013), 1212-1220. | DOI | MR | JFM

[8] Wang, S., Wei, B.: Multiplicative Zagreb indices of $k$-trees. Discrete Appl. Math. 180 (2015), 168-175. | DOI | MR | JFM

[9] West, D. B.: Introduction to Graph Theory. Upper Saddle River, Prentice Hall (1996). | MR | JFM

Cité par Sources :