Hosoya index

The Hosoya index, also known as the Z index, of a graph is the total number of matchings in it. The Hosoya index is always at least one, because the empty set of edges is counted as a matching for this purpose. Equivalently, the Hosoya index is the number of non-empty matchings plus one. The index is named after Haruo Hosoya. It is used as a topological index in chemical graph theory.

Complete graphs have the largest Hosoya index for any given number of vertices; their Hosoya indices are the telephone numbers.

History

This

A linear alkane, for the purposes of the Hosoya index, may be represented as a path graph without any branching. A path with one vertex and no edges (corresponding to the methane molecule) has one (empty) matching, so its Hosoya index is one; a path with one edge (ethane) has two matchings (one with zero edges and one with one edges), so its Hosoya index is two. Propane (a length-two path) has three matchings: either of its edges, or the empty matching. n-butane (a length-three path) has five matchings, distinguishing it from isobutane which has four. More generally, a matching in a path with ${\displaystyle k}$ edges either forms a matching in the first ${\displaystyle k-1}$ edges, or it forms a matching in the first ${\displaystyle k-2}$ edges together with the final edge of the path. This case analysis shows that the Hosoya indices of linear alkanes obey the recurrence governing the

The largest possible value of the Hosoya index, on a graph with ${\displaystyle n}$ vertices, is given by the complete graph ${\displaystyle K_{n}}$. The Hosoya indices for the complete graphs are the telephone numbers

These numbers can be expressed by a summation formula involving factorials, as

$${\displaystyle \sum _{k=0}^{\lfloor n/2\rfloor }{\frac {n!}{2^{k}\cdot k!\cdot \left(n-2k\right)!}}.}$$