Czechoslovak Mathematical Journal, online first, 4 pp.

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

Shaohui Wang, Bing Wei

Received February 12, 2016.   First published March 1, 2017.

Shaohui Wang, Department of Mathematics, The University of Mississippi, University Avenue, University, Mississippi 38677, USA, and Department of Mathematics and Computer Science, Adelphi University, 1 South Ave, Garden City, New York 11530, USA, e-mail: shaohuiwang@yahoo.com; Bing Wei, Department of Mathematics, The University of Mississippi, University Avenue, University, Mississippi 38677, USA, e-mail: bwei@olemiss.edu

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) \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.

Keywords: domination; independent domination

Classification (MSC 2010): 05C05, 05C69

DOI: 10.21136/CMJ.2017.0068-16

Full text available as PDF.


References:
  [1] R. B. Allan, R. Laskar: On domination and independent domination numbers of a graph. Discrete Math. 23 (1978), 73-76. DOI 10.1016/0012-365X(78)90105-X | MR 0523402 | Zbl 0416.05064
  [2] T. Beyer, A. Proskurowski, S. Hedetniemi, S. Mitchell: Independent domination in trees. Proc. Conf. on Combinatorics, Graph Theory and Computing Baton Rouge, 1977, Congressus Numerantium, Utilitas Math., Winnipeg (1977), 321-328. MR 0485473 | Zbl 0417.05020
  [3] M. Furuya, K. Ozeki, A. Sasaki: On the ratio of the domination number and the independent domination number in graphs. Discrete Appl. Math. 178 (2014), 157-159. DOI 10.1016/j.dam.2014.06.005 | MR 3258174 | Zbl 1300.05219
  [4] W. Goddard, M. A. Henning: Independent domination in graphs: A survey and recent results. Discrete Math. 313 (2013), 839-854. DOI 10.1016/j.disc.2012.11.031 | MR 3017969 | Zbl 1260.05113
  [5] W. Goddard, M. A. Henning, J. Lyle, J. Southey: On the independent domination number of regular graphs. Ann. Comb. 16 (2012), 719-732. DOI 10.1007/s00026-012-0155-4 | MR 3000440 | Zbl 1256.05169
  [6] N. J. Rad, L. Volkmann: A note on the independent domination number in graphs. Discrete Appl. Math. 161 (2013), 3087-3089. DOI 10.1016/j.dam.2013.07.009 | MR 3126675 | Zbl 1287.05107
  [7] J. Southey, M. A. Henning: Domination versus independent domination in cubic graphs. Discrete Math. 313 (2013), 1212-1220. DOI 10.1016/j.disc.2012.01.003 | MR 3034752 | Zbl 1277.05129
  [8] S. Wang, B. Wei: Multiplicative Zagreb indices of $k$-trees. Discrete Appl. Math. 180 (2015), 168-175. DOI 10.1016/j.dam.2014.08.017 | MR 3280706 | Zbl 1303.05034
  [9] D. B. West: Introduction to Graph Theory. Upper Saddle River, Prentice Hall (1996). MR 1367739 | Zbl 0845.05001


Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris.cz.
Subscribers of Springer need to access the articles on their site, which is http://link.springer.com/journal/10587.


[List of online first articles] [Contents of Czechoslovak Mathematical Journal]