๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Alternating Whitney sums and matchings in trees, part II

โœ Scribed by Robert E. Jamison

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
846 KB
Volume
79
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

โœฆ Synopsis

The number of k node subtrees of a tree is its kth Whitney number. This paper establishes quadratic bounds in the number of nodes on the alternating sum of the Whitney numbers weighted by k*. The lower bound is achieved precisely for paths on an even number of nodes. The upper bound is achieved for Edmonds' alternating trees. A rooted alternating sum is shown to be related to the Gallai-Edmonds matching decomposition and the structure of maximum independent sets in the tree.

๐Ÿ“œ SIMILAR VOLUMES

Alternating Whitney sums and matchings i
Alternating Whitney sums and matchings in trees, part 1
โœ Robert E Jamison ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 673 KB

The number of k-node subtrees 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 g