✦ LIBER ✦

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

✍ Scribed by Charles Delorme; Odile Favaron; Dieter Rautenbach

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 192 KB
Volume: 130
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00328-7

No coin nor oath required. For personal study only.

✦ Synopsis

We derive closed formulas for the numbers of independent sets of size at most 4 and matchings of size at most 3 in graphs without small cycles that depend only on the degree sequence and the products of the degrees of adjacent vertices.

As a related problem we describe an algorithm that determines a tree of given degree sequence that maximizes the sum of the products of the degrees of adjacent vertices.