×

Threes with \(m\)-matchings and the third minimal Hosoya index. (English) Zbl 1119.05324

The \(m\)-matching of a graph \(G\) is a set of independent edges of \(G\), of cardinality \(m\). It is assumed that the trees considered have \(m\)-matchings, but no \((m+1)\)-matching. The Hosoya index is the total number of independent-edge sets. Trees with a given \(m\) and minimal and second-minimal Hosoya index were determined previously [Y. P. Hou, On acyclic systems with minimal Hosoya index, Discrete Math. 119, 251–257 (2002; Zbl 0999.05020)]. Now also the trees with an \(m\)-matching and with third-minimal Hosoya index are characterized.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
05C35 Extremal problems in graph theory

Keywords:

trees

Citations:

Zbl 0999.05020