Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees

DOI10.1016/S0166-218X(03)00328-7zbMath1020.05053MaRDI QIDQ1408460

Charles Delorme, Dieter Rautenbach, Odile Favaron

Publication date: 22 September 2003

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

zbMATH Keywords

treematchingindependent setdegree sequenceKruskal's algorithm

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (7)

On connected graphs and trees with maximal inverse sum indeg index ⋮ Unnamed Item ⋮ Extremal trees with given degree sequence for the Randić index ⋮ A note on extremal trees with degree conditions ⋮ Extremal Properties of Graphs and Eigencentrality in Trees with a Given Degree Sequence ⋮ Closed formulas for the number of small paths, independent sets and matchings in fullerenes ⋮ On the extremal values of the eccentric distance sum of trees with a given maximum degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Matching theory
• On matching coefficients
• An introduction to matching polynomials
• Extremal graphs for weights
• A note on the number of matchings and independent sets in trees
• A linear-programming approach to the generalized Randić index
• On the theory of the matching polynomial
• On the Randić index

This page was built for publication: Closed formulas for the numbers of small independent sets and matchings and an extremal problem for trees