A Note on Independent Sets in Trees

DOI10.1137/0401012zbMATH Open0646.05036OpenAlexW2050392684MaRDI QIDQ3789596FDOQ3789596

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

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
• On maximal independent sets of nodes in trees

zbMATH Keywords

treeextremal graphsindependent verticesmaximal independent vertex sets

Mathematics Subject Classification ID

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

Cited In (51)

• The maximum number of maximum dissociation sets in trees
• Maximum dissociation sets in subcubic trees
• Maximal independent sets on a grid graph
• A finiteness theorem for maximal independent sets
• The maximum clique problem
• On radius 2 trees with the maximum number of matchings
• The number of maximum matchings in a tree
• On the number of minimal transversals in 3-uniform hypergraphs
• On the Number ofk-Dominating Independent Sets
• Maximum modulus of independence roots of graphs and trees
• Trees with maximum number of maximal matchings
• On generalized independent subsets of trees
• Almost all trees have an even number of independent sets
• On graphs with the third largest number of maximal independent sets
• On the number of 2-packings in a connected graph
• The number of maximal independent sets in trees with a given number of leaves
• The maximum number of maximum generalized 4-independent sets in trees
• Maximal independent sets in bipartite graphs
• Maximal and maximum dissociation sets in general and triangle-free graphs
• The number of maximal independent sets of \((k+1)\)-valent trees
• Independent sets in graphs
• Irredundant and perfect neighbourhood sets in trees
• Constraints on the number of maximal independent sets in graphs
• On maximal independent sets of nodes in trees
• A note on the number of matchings and independent sets in trees
• Coverings, Matchings and the number of maximal independent sets of graphs
• On \(S_0\)-free forests with man independent sets
• Title not available (Why is that?)
• The structure and maximum number of maximum independent sets in trees
• On the maximum number of maximum dissociation sets in trees with given dissociation number
• 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
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Maximal independent sets and maximal matchings in series-parallel and related graph classes
• Generalizing Erdős, Moon and Moser's result -- the number of \(k\)-dominating independent sets
• Title not available (Why is that?)
• Graphs with the second largest number of maximal independent sets
• The number of maximal independent sets in a connected graph
• The minimum number of maximal independent sets in twin-free graphs
• The Number of Maximal Independent Sets in a Tree
• Counting the maximal independent sets in trees with two degrees of maximum degree
• The maximum number of maximal independent sets in unicyclic connected graphs
• On the number of independent sets in a tree
• Maximal independent sets in caterpillar graphs
• Trees with a given number of leaves and the maximal number of maximum independent sets
• On the number of maximal independent sets: From Moon–Moser to Hujter–Tuza
• An independent dominating set in the complement of a minimum dominating set of a tree
• The independent set sequence of some families of trees
• The number of maximal independent sets in connected triangle-free graphs
• Graphs, partitions and Fibonacci numbers
• Maximal independent sets in graphs with at most one cycle

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)