# Article

 Title: A note on the independent domination number of subset graph (English) Author: Chen, Xue-Gang Author: Ma, De-xiang Author: Xing, Hua-Ming Author: Sun, Liang Language: English Journal: Czechoslovak Mathematical Journal ISSN: 0011-4642 (print) ISSN: 1572-9141 (online) Volume: 55 Issue: 2 Year: 2005 Pages: 511-517 Summary lang: English . Category: math . Summary: The independent domination number $i(G)$ (independent number $\beta (G)$) is the minimum (maximum) cardinality among all maximal independent sets of $G$. Haviland (1995) conjectured that any connected regular graph $G$ of order $n$ and degree $\delta \le \frac{1}{2}{n}$ satisfies $i(G)\le \lceil \frac{2n}{3\delta }\rceil \frac{1}{2}{\delta }$. For $1\le k\le l\le m$, the subset graph $S_{m}(k,l)$ is the bipartite graph whose vertices are the $k$- and $l$-subsets of an $m$ element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for $i(S_{m}(k,l))$ and prove that if $k+l=m$ then Haviland’s conjecture holds for the subset graph $S_{m}(k,l)$. Furthermore, we give the exact value of $\beta (S_{m}(k,l))$. (English) Keyword: independent domination number Keyword: independent number Keyword: subset graph MSC: 05C35 MSC: 05C69 idZBL: Zbl 1081.05082 idMR: MR2137158 . Date available: 2009-09-24T11:25:10Z Last updated: 2016-04-07 Stable URL: http://hdl.handle.net/10338.dmlcz/127998 . Reference: [1] E. J.  Cockayne and S. T. Hedetniemi: Independence graphs.Proc. 5th Southeast Conf. Comb. Graph Theor. Comput, Utilitas Math., Boca Raton, 1974, pp. 471–491. MR 0357174 Reference: [2] O.  Favaron: Two relations between the parameters of independence and irredundance.Discrete Math. 70 (1988), 17–20. MR 0943719, 10.1016/0012-365X(88)90076-3 Reference: [3] J.  Haviland: On minimum maximal independent sets of a graph.Discrete Math. 94 (1991), 95–101. Zbl 0758.05061, MR 1139586, 10.1016/0012-365X(91)90318-V Reference: [4] J.  Haviland: Independent domination in regular graphs.Discrete Math. 143 (1995), 275–280. Zbl 0838.05065, MR 1344759, 10.1016/0012-365X(94)00022-B Reference: [5] M. A.  Henning and P. J.  Slater: Inequality relating domination parameters in cubic graphs.Discrete Math. 158 (1996), 87–98. MR 1411112, 10.1016/0012-365X(96)00025-8 Reference: [6] E. J.  Cockayne, O.  Favaron, C.  Payan and A. G.  Thomason: Contributions to the theory of domination, independence and irredundance in graphs.Discrete Math. 33 (1981), 249–258. MR 0602041, 10.1016/0012-365X(81)90268-5 Reference: [7] P. C. B.  Lam, W. C.  Shiu and L.  Sun: On independent domination number of regular graphs.Discrete Math. 202 (1999), 135–144. MR 1694509, 10.1016/S0012-365X(98)00350-1 .

## Files

Files Size Format View
CzechMathJ_55-2005-2_22.pdf 282.2Kb application/pdf View/Open

Partner of