Chen, Xue-Gang, et al. "A note on the independent domination number of subset graph." Czechoslovak Mathematical Journal 55.2 (2005): 511-517. <http://eudml.org/doc/30965>.
@article{Chen2005,
abstract = {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))$.},
author = {Chen, Xue-Gang, Ma, De-xiang, Xing, Hua Ming, Sun, Liang},
journal = {Czechoslovak Mathematical Journal},
keywords = {independent domination number; independent number; subset graph; independent domination number; independent number; subset graph},
language = {eng},
number = {2},
pages = {511-517},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A note on the independent domination number of subset graph},
url = {http://eudml.org/doc/30965},
volume = {55},
year = {2005},
}
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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 55
IS - 2
SP - 511
EP - 517
AB - 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))$.
LA - eng
KW - independent domination number; independent number; subset graph; independent domination number; independent number; subset graph
UR - http://eudml.org/doc/30965
ER -
