A note on the independent domination number versus the domination number in bipartite graphs
Czechoslovak Mathematical Journal (2017)
- Volume: 67, Issue: 2, page 533-536
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow to cite
topWang, 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- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- West, D. B., Introduction to Graph Theory, Upper Saddle River, Prentice Hall (1996). (1996) Zbl0845.05001MR1367739
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.