Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
independent domination number; independent number; subset graph
independent domination number; independent number; subset graph
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))$.
References:
[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
[2] O. Favaron: Two relations between the parameters of independence and irredundance. Discrete Math. 70 (1988), 17–20. DOI 10.1016/0012-365X(88)90076-3 | MR 0943719
[3] J. Haviland: On minimum maximal independent sets of a graph. Discrete Math. 94 (1991), 95–101. DOI 10.1016/0012-365X(91)90318-V | MR 1139586 | Zbl 0758.05061
[4] J. Haviland: Independent domination in regular graphs. Discrete Math. 143 (1995), 275–280. DOI 10.1016/0012-365X(94)00022-B | MR 1344759 | Zbl 0838.05065
[5] M. A. Henning and P. J. Slater: Inequality relating domination parameters in cubic graphs. Discrete Math. 158 (1996), 87–98. DOI 10.1016/0012-365X(96)00025-8 | MR 1411112
[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. DOI 10.1016/0012-365X(81)90268-5 | MR 0602041
[7] P. C. B. Lam, W. C. Shiu and L. Sun: On independent domination number of regular graphs. Discrete Math. 202 (1999), 135–144. DOI 10.1016/S0012-365X(98)00350-1 | MR 1694509
Search
Partner of
