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/