Maximal and maximum independent sets in graphs with at mostr cycles

DOI10.1002/jgt.20186zbMath1107.05047arXivmath/0505048OpenAlexW2950136068MaRDI QIDQ3418195

Bruce E. Sagan, Vincent R. Vatter

Publication date: 2 February 2007

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0505048

zbMATH Keywords

cycle ear decomposition

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 (19)

Maximal and maximum dissociation sets in general and triangle-free graphs ⋮ Maximal independent sets on a grid graph ⋮ Maximizing the number of independent sets of fixed size in connected graphs with given independence number ⋮ The maximum number of maximum dissociation sets in trees ⋮ On the maximum number of maximum independent sets in connected graphs ⋮ Counting maximal independent sets in some \(n\)-gonal cacti ⋮ Maximum dissociation sets in subcubic trees ⋮ On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number ⋮ Minimum number of maximal dissociation sets in trees ⋮ On the maximum number of maximum dissociation sets in trees with given dissociation number ⋮ 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 ⋮ On the maximum number of cliques in a graph ⋮ Satisfiability of mixed Horn formulas ⋮ Graphs with the second largest number of maximal independent sets ⋮ Maximal independent sets and maximal matchings in series-parallel and related graph classes ⋮ Maximal independent sets in caterpillar graphs

This page was built for publication: Maximal and maximum independent sets in graphs with at mostr cycles