Trees with the second largest number of maximal independent sets

被引：12

作者：

Jou, Min-Jen ^{[1
]}

Lin, Jenq-Jong ^{[1
]}

机构：

[1] Ling Tung Univ, Taichung 40852, Taiwan

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 13期

关键词：

Maximal independent set; Tree; Forest; Extremal graph; FIBONACCI NUMBERS; GRAPHS;

D O I：

10.1016/j.disc.2009.02.007

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all trees and forests of order n >= 4. We also characterize those extremal graphs achieving these values. (C) 2009 Published by Elsevier B.V.

引用

页码：4469 / 4474

页数：6

共 10 条

[1] THE NUMBER OF MAXIMAL INDEPENDENT SETS IN TRIANGLE-FREE GRAPHS [J].