Geodesic
A note on the independent domination number of subset graph
Czechoslovak Mathematical Journal, Tome 55 (2005) no. 2, pp. 511-517
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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))$.
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))$.
Classification : 05C35, 05C69
Keywords: independent domination number; independent number; subset graph 
@article{CMJ_2005_55_2_a21,
     author = {Chen, Xue-Gang and Ma, De-xiang and Xing, Hua-Ming and Sun, Liang},
     title = {A note on the independent domination number of subset graph},
     journal = {Czechoslovak Mathematical Journal},
     pages = {511--517},
     year = {2005},
     volume = {55},
     number = {2},
     mrnumber = {2137158},
     zbl = {1081.05082},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a21/}
}
TY  - JOUR
AU  - Chen, Xue-Gang
AU  - Ma, De-xiang
AU  - Xing, Hua-Ming
AU  - Sun, Liang
TI  - A note on the independent domination number of subset graph
JO  - Czechoslovak Mathematical Journal
PY  - 2005
SP  - 511
EP  - 517
VL  - 55
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a21/
LA  - en
ID  - CMJ_2005_55_2_a21
ER  - 
%0 Journal Article
%A Chen, Xue-Gang
%A Ma, De-xiang
%A Xing, Hua-Ming
%A Sun, Liang
%T A note on the independent domination number of subset graph
%J Czechoslovak Mathematical Journal
%D 2005
%P 511-517
%V 55
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a21/
%G en
%F CMJ_2005_55_2_a21
Chen, Xue-Gang; Ma, De-xiang; Xing, Hua-Ming; Sun, Liang. A note on the independent domination number of subset graph. Czechoslovak Mathematical Journal, Tome 55 (2005) no. 2, pp. 511-517. http://geodesic.mathdoc.fr/item/CMJ_2005_55_2_a21/

[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

[2] O.  Favaron: Two relations between the parameters of independence and irredundance. Discrete Math. 70 (1988), 17–20. | DOI | MR

[3] J.  Haviland: On minimum maximal independent sets of a graph. Discrete Math. 94 (1991), 95–101. | DOI | MR | Zbl

[4] J.  Haviland: Independent domination in regular graphs. Discrete Math. 143 (1995), 275–280. | DOI | MR | Zbl

[5] M. A.  Henning and P. J.  Slater: Inequality relating domination parameters in cubic graphs. Discrete Math. 158 (1996), 87–98. | DOI | MR

[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 | MR

[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 | MR