MAXIMAL INDEPENDENT SETS IN BIPARTITE GRAPHS

被引：32
作者：
LIU, JQ
机构：
[1] Department of Mathematics and Statistics, Western Michigan University, Kalamazoo, Michigan
来源：
JOURNAL OF GRAPH THEORY | 1993年 / 17卷 / 04期
关键词：
D O I：
10.1002/jgt.3190170407
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order n and the extremal graphs as well as the corresponding results for connected bipartite graphs. (C) 1993 John Wiley & Sons, Inc.
引用
收藏
页码：495 / 507
页数：13
相关论文
共 7 条
[1]   THE NUMBER OF MAXIMAL INDEPENDENT SETS IN CONNECTED GRAPHS [J].
FUREDI, Z .
JOURNAL OF GRAPH THEORY, 1987, 11 (04) :463-470
[2]   THE NUMBER OF MAXIMAL INDEPENDENT SETS IN A CONNECTED GRAPH [J].
GRIGGS, JR ;
GRINSTEAD, CM ;
GUICHARD, DR .
DISCRETE MATHEMATICS, 1988, 68 (2-3) :211-220
[3]  
LIU J, 1992, THESIS W MICHIGAN U
[4]  
MILLER RE, 1960, IBM RC240 JT WATS RE
[5]   ON CLIQUES IN GRAPHS [J].
MOON, JW ;
MOSER, L .
ISRAEL JOURNAL OF MATHEMATICS, 1965, 3 (01) :23-&
[6]  
SAGAN BE, 1988, SIAM J DISCRETE MATH, P105
[7]   THE NUMBER OF MAXIMAL INDEPENDENT SETS IN A TREE [J].
WILF, HS .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (01) :125-130
1