| 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:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127998 |
| . |
| 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 |
| . |
