The number of maximum independent sets in graphs

被引：43

作者：

Jou, MJ ^{[1
]}

Chang, GJ

机构：

[1] Ling Tong Coll, Taichung, Taiwan

[2] Natl Chiao Tung Univ, Dept Appl Math, Hsinchu 300, Taiwan

来源：

TAIWANESE JOURNAL OF MATHEMATICS | 2000年 / 4卷 / 04期

关键词：

independent set; tree; forest; connected graph; cycle; triangle; leaf; distance;

D O I：

10.11650/twjm/1500407302

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper, we study the problem of determining the largest number of maximum independent sets of a graph of order n. Solutions to this problem are given for various classes of graphs, including general graphs, trees, forests, (connected) graphs with at most one cycle, connected graphs and triangle-free graphs. Extremal graphs achieving the maximum values are also given.

引用

页码：685 / 695

页数：11

共 28 条

[1]

Chang GJ, 1999, DISCRETE MATH, V197, P169

[2]

Cohen D., 1984, SEM LOTH COMB 10 SES, P48

[3]

FAN C, 1991, GRAPH THEORY COMBINA, P140

[4] AN UPPER BOUND ON THE NUMBER OF CLIQUES IN A GRAPH [J].