| Title:
|
A note on the independent domination number versus the domination number in bipartite graphs (English) |
| Author:
|
Wang, Shaohui |
| Author:
|
Wei, Bing |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
67 |
| Issue:
|
2 |
| Year:
|
2017 |
| Pages:
|
533-536 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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, 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. (English) |
| Keyword:
|
domination |
| Keyword:
|
independent domination |
| MSC:
|
05C05 |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 06738536 |
| idMR:
|
MR3661058 |
| DOI:
|
10.21136/CMJ.2017.0068-16 |
| . |
| Date available:
|
2017-06-01T14:32:20Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146773 |
| . |
| Reference:
|
[1] Allan, R. B., Laskar, R.: On domination and independent domination numbers of a graph.Discrete Math. 23 (1978), 73-76. Zbl 0416.05064, MR 0523402, 10.1016/0012-365X(78)90105-X |
| Reference:
|
[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. Zbl 0417.05020, MR 0485473 |
| Reference:
|
[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. Zbl 1300.05219, MR 3258174, 10.1016/j.dam.2014.06.005 |
| Reference:
|
[4] Goddard, W., Henning, M. A.: Independent domination in graphs: A survey and recent results.Discrete Math. 313 (2013), 839-854. Zbl 1260.05113, MR 3017969, 10.1016/j.disc.2012.11.031 |
| Reference:
|
[5] Goddard, W., Henning, M. A., Lyle, J., Southey, J.: On the independent domination number of regular graphs.Ann. Comb. 16 (2012), 719-732. Zbl 1256.05169, MR 3000440, 10.1007/s00026-012-0155-4 |
| Reference:
|
[6] Rad, N. J., Volkmann, L.: A note on the independent domination number in graphs.Discrete Appl. Math. 161 (2013), 3087-3089. Zbl 1287.05107, MR 3126675, 10.1016/j.dam.2013.07.009 |
| Reference:
|
[7] Southey, J., Henning, M. A.: Domination versus independent domination in cubic graphs.Discrete Math. 313 (2013), 1212-1220. Zbl 1277.05129, MR 3034752, 10.1016/j.disc.2012.01.003 |
| Reference:
|
[8] Wang, S., Wei, B.: Multiplicative Zagreb indices of $k$-trees.Discrete Appl. Math. 180 (2015), 168-175. Zbl 1303.05034, MR 3280706, 10.1016/j.dam.2014.08.017 |
| Reference:
|
[9] West, D. B.: Introduction to Graph Theory.Upper Saddle River, Prentice Hall (1996). Zbl 0845.05001, MR 1367739 |
| . |
