Alternating Whitney sums and matchings in trees. 1 (Q1105614)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Alternating Whitney sums and matchings in trees. 1 |
scientific article; zbMATH DE number 4059429
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Alternating Whitney sums and matchings in trees. 1 |
scientific article; zbMATH DE number 4059429 |
Statements
Alternating Whitney sums and matchings in trees. 1 (English)
0 references
1987
0 references
The number of k-node subtress of a tree is its kth Whitney number. This paper investigates the behavior of certain alternating sums of these Whitney numbers and shows how they are related to the structure of maximum matchings in the tree. It is shown that the alternating sum of the Whitney numbers gives the maximum cardinality of an independent set of nodes. Moreover, a weighted alternating sum yields the number of nodes left uncovered by at least one maximum matching.
0 references
Whitney number
0 references
maximum matchings
0 references
tree
0 references
0.98560596
0 references
0.8661787
0 references
0.85944855
0 references
0 references
0 references
0 references
0.8451964
0 references
0.8447809
0 references
