Hosoya index

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.

[2][3] In his article, "The Topological Index Z Before and After 1971," on the history of the notion and the associated inside stories, Hosoya writes that he introduced the Z index to report a good correlation of the boiling points of alkane isomers and their Z indices, basing on his unpublished 1957 work carried out while he was an undergraduate student at the University of Tokyo.

[2] A linear alkane, for the purposes of the Hosoya index, may be represented as a path graph without any branching.

n-butane (a length-three path) has five matchings, distinguishing it from isobutane which has four.

This case analysis shows that the Hosoya indices of linear alkanes obey the recurrence governing the Fibonacci numbers, and because they also have the same base case they must equal the Fibonacci numbers.

The structure of the matchings in these graphs may be visualized using a Fibonacci cube.

Every graph that is not complete has a smaller Hosoya index than this upper bound.

[4] The Hosoya index is #P-complete to compute, even for planar graphs.

[5] However, it may be calculated by evaluating the matching polynomial mG at the argument 1.

[6] Based on this evaluation, the calculation of the Hosoya index is fixed-parameter tractable for graphs of bounded treewidth[7] and polynomial (with an exponent that depends linearly on the width) for graphs of bounded clique-width.