Graphs with the second largest number of maximal independent sets

DOI10.1016/j.disc.2007.10.032zbMath1219.05122OpenAlexW2006825168MaRDI QIDQ998481

Ze-min Jin, Xue Liang Li

Publication date: 28 January 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2007.10.032

zbMATH Keywords

extremal graphmaximal (maximum) independent set

Mathematics Subject Classification ID

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

Related Items

The number of maximal independent sets in trees with a given number of leaves ⋮ On rejected arguments and implicit conflicts: the hidden power of argumentation semantics ⋮ The second largest number of maximal independent sets in connected graphs with at most one cycle ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ Independent sets in graphs ⋮ On graphs with the third largest number of maximal independent sets ⋮ On the third largest number of maximal independent sets of graphs ⋮ On the \(k\)-component independence number of a tree ⋮ Trees with the second largest number of maximal independent sets

Cites Work

• 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
• The number of maximal independent sets in connected triangle-free graphs
• Maximal independent sets in graphs with at most one cycle
• A finiteness theorem for maximal independent sets
• Maximal independent sets in bipartite graphs
• Maximal independent sets in graphs with at mostr cycles
• Maximal and maximum independent sets in graphs with at mostr cycles
• 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
• The number of maximum independent sets in graphs