The number of maximal independent sets in connected triangle-free graphs

DOI10.1016/S0012-365X(99)90057-2zbMath0929.05062OpenAlexW4229603427MaRDI QIDQ1292823

Min-Jen Jou, Gerard Jennhwa Chang

Publication date: 9 August 1999

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(99)90057-2

zbMATH Keywords

extremal graphstriangle-free graphmaximal independent sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ Maximal independent sets in grid graphs ⋮ The maximum number of maximal independent sets in unicyclic connected graphs ⋮ Independent sets in graphs ⋮ On graphs with the third largest number of maximal independent sets ⋮ Coverings, Matchings and the number of maximal independent sets of graphs ⋮ Graphs with the second largest number of maximal independent sets ⋮ Maximal independent sets and regularity of graphs ⋮ Maximal independent sets in caterpillar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The cardinality of the collection of maximum independent sets of a functional graph
• The maximum number of cliques in dense graphs
• Graphs with unique maximum independent sets
• The number of maximal independent sets in a connected graph
• On generating all maximal independent sets
• Maximal independent sets in graphs with at most one cycle
• Bipartite graphs can have any number of independent sets
• A finiteness theorem for maximal independent sets
• Maximal independent sets in bipartite graphs
• The Number of Maximal Independent Sets in a Tree
• A Note on Independent Sets in Trees
• The number of maximal independent sets in connected graphs
• On maximal independent sets of nodes in trees
• The structure and maximum number of maximum independent sets in trees
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• An upper bound on the number of cliques in a graph
• On cliques in graphs