Alternating Whitney sums and matchings in trees. 1 (Q1105614)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Alternating Whitney sums and matchings in trees. 1 |
scientific article |
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
