Previous |  Up |  Next


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:
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 Size Format View
CzechMathJ_55-2005-2_22.pdf 282.2Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo