The number of maximal independent sets of (k + 1)-valent trees

被引：0

作者：

Song J. ^{[1
,2
]}

Han H. ^{[2
]}

Lee C. ^{[2
]}

机构：

[1] Department of Mathematics, University of Seoul

来源：

Journal of Applied Mathematics and Computing | 2006年 / 21卷 / 1-2期

关键词：

Binary tree; Maximal independent set; Trivalent tree;

D O I：

10.1007/BF02896409

中图分类号：

学科分类号：

摘要：

We classify maximal independent sets of (k + 1)-valent trees into two groups, namely, type A and type B maximal independent sets and consider specific independent sets of these trees. We study relations among these three types of independent sets. Using the relations, we count the number of all maximal independent sets of (k + 1)-valent trees with n vertices of degree k + 1. © 2006 Korean Society for Computational & Applied Mathamatics and Korean SIGCAM.

引用

页码：315 / 324

页数：9

共 13 条

[1]

Griggs J. R.(1988)The number of maximal independent sets in a connected graph Discrete Math. 68 211-220

[2]

Grinstead C. M.(1964)The number of plane trees Proc. Kon. Ned. Akad. v. Wetensch. 67 319-329

[3]

Guichard D. R.(2003)The number of independent dominating sets of labeled trees Commun. Korean Math. Soc. 18 181-192

[4]

Harary F.(2005)The Number of Independent Dominating Sets of Unlabeled Trees J. Appl. Math. & Computing 18 639-647

[5]

Prins G.(1965)On cliques in graphs Israel J. Math. 3 23-28

[6]

Tutte W. T.(1988)A note on independent sets in trees SIAM. J. Discrete Math. 1 105-108

[7]

Lee C.(1986)The number of maximal independent sets in a tree SIAM J. Alg. Discrete Math. 7 125-130

[8]

Lee C.(undefined)undefined undefined undefined undefined-undefined

[9]

Cho S.(undefined)undefined undefined undefined undefined-undefined

[10]

Moon J. W.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →