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.
Reviewer: Ivan Gutman (Kragujevac)
MSC:
05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
05C05 | Trees |
05C35 | Extremal problems in graph theory |