A Note on Independent Sets in Trees

DOI10.1137/0401012MaRDI QIDQ3789596zbMATH OpenOpenAlexFDO

Authors Bruce E. Sagan

Publication date 1988

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0401012

zbMATH Keywords

extremal graphsindependent verticesmaximal independent vertex setstree

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Independent sets in trees
• On independent \([1, 2]\)-sets in trees
• On the number of independent sets in a tree
• On generalized independent subsets of trees
• scientific article; zbMATH DE number 6470693
• On the independent set sequence of a tree
• A note on the number of matchings and independent sets in trees
• On intersecting families of independent sets in trees
• scientific article; zbMATH DE number 179305
• On maximal independent sets of nodes in trees

Cited in

(59)

• An independent dominating set in the complement of a minimum dominating set of a tree
• The number of maximal independent sets in a connected graph
• The number of maximal independent sets in connected triangle-free graphs
• The maximum clique problem
• Maximal independent sets in graphs with at most one cycle
• Irredundant and perfect neighbourhood sets in trees
• Generalizing Erdős, Moon and Moser's result -- the number of \(k\)-dominating independent sets
• On the number of 2-packings in a connected graph
• A note on the number of matchings and independent sets in trees
• Trees with a given number of leaves and the maximal number of maximum independent sets
• The number of maximal independent sets in trees with a given number of leaves
• Maximal and maximum dissociation sets in general and triangle-free graphs
• Maximum modulus of independence roots of graphs and trees
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Graphs, partitions and Fibonacci numbers
• Almost all trees have an even number of independent sets
• Maximal independent sets on a grid graph
• Maximal buttonings of trees
• The number of maximal independent sets of \((k+1)\)-valent trees
• A finiteness theorem for maximal independent sets
• On S₀-free forests with man independent sets
• scientific article; zbMATH DE number 6376879 (Why is no real title available?)
• On the number of k-dominating independent sets
• Counting the maximal independent sets in trees with two degrees of maximum degree
• Maximal independent sets in bipartite graphs
• The Number of Maximal Independent Sets in a Tree
• On maximal independent sets of nodes in trees
• On generalized independent subsets of trees
• The structure and maximum number of maximum independent sets in trees
• scientific article; zbMATH DE number 179305 (Why is no real title available?)
• The number of maximum matchings in a tree
• Constraints on the number of maximal independent sets in graphs
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Independent sets in graphs
• Maximal trees with log-concave independence polynomials
• The independent set sequence of some families of trees
• Coverings, matchings and the number of maximal independent sets of graphs
• The maximum number of maximum dissociation sets in trees
• On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza
• On radius 2 trees with the maximum number of matchings
• Maximum dissociation sets in subcubic trees
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• The maximum number of maximum generalized 4-independent sets in trees
• The minimum number of maximal independent sets in twin-free graphs
• Maximum generalized 4-independent sets in subcubic trees
• Binary trees with extremal number of maximal independent sets
• Maximal independent sets in graphs with a given matching number
• The maximum number of maximum dissociation sets in potted graphs
• Upper bound for the number of maximal dissociation sets in trees
• The minimum number of maximal independent sets in graphs with given order and independence number
• Maximal independent sets in caterpillar graphs
• Trees with maximum number of maximal matchings
• The maximum number of maximal independent sets in unicyclic connected graphs
• On the number of minimal transversals in 3-uniform hypergraphs
• On the existence and on the number of (k,l)-kernels in the lexicographic product of graphs
• Trees with extremal numbers of maximal independent sets including the set of leaves
• On graphs with the third largest number of maximal independent sets
• On the number of independent sets in a tree
• Graphs with the second largest number of maximal independent sets

This page was built for publication: A Note on Independent Sets in Trees

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