zbMATH — the first resource for mathematics

Maximal independent sets in bipartite graphs. (English) Zbl 0783.05063
The author shows that a bipartite graph with \(n\) vertices can have at most \(2^{[n/2]}\) maximal independent sets of vertices and he characterizes the extremal graphs. He also solves the corresponding problem for connected bipartite graphs with \(n\) vertices. M. Hujter and Zs. Tuza [SIAM J. Discrete Math. 6, 284-288 (1993; Zbl 0779.05025)] have considered the corresponding problem for triangle-free graphs.

05C35 Extremal problems in graph theory
Full Text: DOI
[1] Füredi, J. Graph Theory 11 pp 463– (1987)
[2] Griggs, Discrete Math. 68 pp 211– (1988)
[3] Maximal and maximum independent sets in graphs. Ph. D. dissertation, Department of Mathematics and Statistics, Western Michigan University (1992).
[4] and , A problem of maximum consistent subsets. IBM Research Report RC-240, J. T. Watson Research Center, Yorktown Heights, NY (1960).
[5] Moon, Isr. J. Math. 3 pp 23– (1965)
[6] A note on independent sets in trees. SIAM J. Discrete Math. (1988) 105–108. · Zbl 0646.05036
[7] Wilf, SIAM J. Alg. Discrete Meth. 7 pp 125– (1986)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.