A note on the number of matchings and independent sets in trees

DOI10.1016/j.dam.2004.07.001zbMath1056.05035MaRDI QIDQ1765528

Miranca Fischermann, Lutz Volkmann, Dieter Rautenbach

Publication date: 23 February 2005

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

Full work available at URL: https://doi.org/10.1016/j.dam.2004.07.001

zbMATH Keywords

Matching; Stable set; Hosoya index; Merrifield-Simmons index; Independent set; Tree

Mathematics Subject Classification ID

05C05: Trees

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

Related Items

On the number of \(k\)-matchings in graphs, On the number of matchings of graphs formed by a graph operation, The smallest hosoya index in \((n,n+1)\)-graphs, Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees, The Merrifield-Simmons index and Hosoya index of \(C(n, k, \lambda)\) graphs, The minimum Merrifield-Simmons index of unicyclic graphs with diameter at most four, The largest Hosoya index of \((n,n+1)\)-graphs, The smallest Merrifield-Simmons index of \((n,n+1)\)-graphs

Cites Work

• On some counting polynomials in chemistry
• An introduction to matching polynomials
• Higher-order Fibonacci numbers
• On the theory of the matching polynomial
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item