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.

Contents 1 History 2 Example 3 Algorithms 4 Notes 5 References

[edit] History

This graph invariant was introduced by Haruo Hosoya in 1971.^[1] It is often used in chemoinformatics for investigations of organic compounds.^[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]

[edit] Example

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 k edges either forms a matching in the first k − 1 edges, or it forms a matching in the first k − 2 edges together with the final edge of the path. Thus, the Hosoya indices of linear alkanes obey the recurrence governing the Fibonacci numbers. Ths structure of the matchings in these graphs may be visualized using a Fibonacci cube.

[edit] Algorithms

The Hosoya index may be computed in an amount of time exponential in the number of edges of the graph.^[4]

[edit] Notes

[edit] References

• Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors", Wiley-VCH, ISBN 3527299130