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

Shaohui Wang; Bing Wei

Czechoslovak Mathematical Journal (2017)

  • Volume: 67, Issue: 2, page 533-536
  • ISSN: 0011-4642

Abstract

top
Let and be the domination number and the independent domination number of , respectively. Rad and Volkmann posted a conjecture that for any graph , where 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 are provided as well.

How to cite

top

Wang, Shaohui, and Wei, Bing. "A note on the independent domination number versus the domination number in bipartite graphs." Czechoslovak Mathematical Journal 67.2 (2017): 533-536. <http://eudml.org/doc/288208>.

@article{Wang2017,
abstract = {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) \le \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.},
author = {Wang, Shaohui, Wei, Bing},
journal = {Czechoslovak Mathematical Journal},
keywords = {domination; independent domination},
language = {eng},
number = {2},
pages = {533-536},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A note on the independent domination number versus the domination number in bipartite graphs},
url = {http://eudml.org/doc/288208},
volume = {67},
year = {2017},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 67
IS - 2
SP - 533
EP - 536
AB - 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) \le \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.
LA - eng
KW - domination; independent domination
UR - http://eudml.org/doc/288208
ER -

References

top
  1. Allan, R. B., Laskar, R., 10.1016/0012-365X(78)90105-X, Discrete Math. 23 (1978), 73-76. (1978) Zbl0416.05064MR0523402DOI10.1016/0012-365X(78)90105-X
  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. (1977) Zbl0417.05020MR0485473
  3. Furuya, M., Ozeki, K., Sasaki, A., 10.1016/j.dam.2014.06.005, Discrete Appl. Math. 178 (2014), 157-159. (2014) Zbl1300.05219MR3258174DOI10.1016/j.dam.2014.06.005
  4. Goddard, W., Henning, M. A., 10.1016/j.disc.2012.11.031, Discrete Math. 313 (2013), 839-854. (2013) Zbl1260.05113MR3017969DOI10.1016/j.disc.2012.11.031
  5. Goddard, W., Henning, M. A., Lyle, J., Southey, J., 10.1007/s00026-012-0155-4, Ann. Comb. 16 (2012), 719-732. (2012) Zbl1256.05169MR3000440DOI10.1007/s00026-012-0155-4
  6. Rad, N. J., Volkmann, L., 10.1016/j.dam.2013.07.009, Discrete Appl. Math. 161 (2013), 3087-3089. (2013) Zbl1287.05107MR3126675DOI10.1016/j.dam.2013.07.009
  7. Southey, J., Henning, M. A., 10.1016/j.disc.2012.01.003, Discrete Math. 313 (2013), 1212-1220. (2013) Zbl1277.05129MR3034752DOI10.1016/j.disc.2012.01.003
  8. Wang, S., Wei, B., 10.1016/j.dam.2014.08.017, Discrete Appl. Math. 180 (2015), 168-175. (2015) Zbl1303.05034MR3280706DOI10.1016/j.dam.2014.08.017
  9. West, D. B., Introduction to Graph Theory, Upper Saddle River, Prentice Hall (1996). (1996) Zbl0845.05001MR1367739

NotesEmbed ?

top

You must be logged in to post comments.