×

The maximum number of maximal independent sets in unicyclic connected graphs. (English) Zbl 1207.05142

Summary: We determine the maximum number of maximal independent sets in a unicyclic connected graph. We also find a class of graphs achieving this maximum value.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Furedi, Z., The number of maximal independent sets in connected graphs, J. Graph Theory, 11, 463-470 (1987) · Zbl 0647.05032
[2] Goh, C. Y.; Koh, K. M.; Sagan, B. E.; Vatter, V. R., Maximal independent sets in a graph with at most \(r\) cycles, J. Graph Theory, 53, 4, 270-282 (2006) · Zbl 1107.05044
[3] Griggs, J. R.; Grinstead, C. M.; Guichard, D. R., The number of maximal independent sets in a connected graph, Discrete Math., 68, 211-220 (1988) · Zbl 0652.05027
[4] Hujter, M.; Tuza, Z., The number of maximal independent sets in triangle-free graphs, SIAM J. Discrete Math., 6, 284-288 (1993) · Zbl 0779.05025
[5] Jou, M. J.; Chang, G. J., Maximal independent sets in graphs with at most one cycle, Discrete Appl. Math., 79, 67-73 (1997) · Zbl 0883.05076
[6] Jou, M. J.; Chang, G. J., The number of maximal independent sets in connected triangle-free graphs, Discrete Math., 197/198, 169-178 (1999) · Zbl 0929.05062
[7] Moon, J. W.; Moser, L., On cliques in graphs, Israel J. Math., 3, 23-28 (1965) · Zbl 0144.23205
[8] Pedersen, A. S.; Vestergaard, P. D., The number of independent sets in unicyclic graphs, Discrete Appl. Math., 152, 246-256 (2005) · Zbl 1080.05069
[9] Sagan, B. E., A note on independent sets in trees, SIAM J. Discrete Math., 1, 105-108 (1988) · Zbl 0646.05036
[10] Sagan, B. E.; Vatter, V. R., Maximal and maximum independent sets in graphs with at most \(r\) cycles, J. Graph Theory, 53, 4, 283-314 (2006) · Zbl 1107.05047
[11] Wilf, H. S., The number of maximal independent sets in a tree, SIAM J. Algebraic Discrete Methods, 7, 125-221 (1986) · Zbl 0584.05024
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.