A finiteness theorem for maximal independent sets

DOI10.1007/BF01858464MaRDI QIDQ2563420zbMATH OpenFDO

Authors Min-Jen Jou, Chiang Lin, Tze-Heng Ma, Gerard Jennhwa Chang

Publication date 12 December 1996

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01858464

zbMATH Keywords

maximal independent sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

Let \(G\) denote a graph with no isolated vertices and with no two vertices that have the same neighbourhood. The authors show, among other things, that if \(G\) has exactly \(k\) maximal independent sets of vertices, where \(k\geq 2\), then \(G\) has at most \(2^{k-1} + k-2\) vertices.

Recommendations

• The Number of Maximal Independent Sets in Triangle-Free Graphs
• On the number of maximum independent sets of graphs
• On graphs having maximal independent sets of exactly \(t\) distinct cardinalities
• On the number of maximal independent sets in a graph

Cites work

• A Note on Independent Sets in Trees
• Maximal independent sets in bipartite graphs
• On cliques in graphs
• On maximal independent sets of nodes in trees
• The number of maximal independent sets in a connected graph
• The Number of Maximal Independent Sets in a Tree
• The number of maximal independent sets in connected graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The structure and maximum number of maximum independent sets in trees

Cited in

(11)

• The number of maximal independent sets in connected triangle-free graphs
• On unique independent sets in graphs
• Maximal independent families and a topological consequence
• On graphs having maximal independent sets of exactly \(t\) distinct cardinalities
• Perfect independent sets with respect to infinitely many relations
• scientific article; zbMATH DE number 4057545 (Why is no real title available?)
• scientific article; zbMATH DE number 845597 (Why is no real title available?)
• Independent sets in graphs
• Maximal independent sets in caterpillar graphs
• Trees with maximum number of maximal matchings
• Graphs with the second largest number of maximal independent sets

This page was built for publication: A finiteness theorem for maximal independent sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2563420)