A note on the independent domination number of subset graph |
| |
Authors: | Email author" target="_blank">Xue-gang?ChenEmail author De-xiang?Ma Hua-Ming?Xing Liang?Sun |
| |
Institution: | (1) Dept. of Math., Shantou University, Shantou, Guangdong, 515063, P.R. China;(2) The College of Information Science and Engineering, Shandong University of Science and Technology, Taian, Shandong Province, 271019, P.R. China;(3) Dept. of Mathematics, Langfang Normal College, Langfang, Hebei, 065000, P.R. China;(4) Department of Applied Mathematics, Beijing Institute of Technology, Beijing, 100081, P.R. China |
| |
Abstract: | The independent domination number i(G) (independent number (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 1/2n satisfies i(G) 2n/3 1/2. For 1 k l 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 Havilands conjecture holds for the subset graph S
m
(k, l). Furthermore, we give the exact value of (S
m
(k, l)).This work was supported by National Natural Sciences Foundation of China (19871036). |
| |
Keywords: | independent domination number independent number subset graph |
本文献已被 SpringerLink 等数据库收录! |
|