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.

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]}

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 edges either forms a matching in the first edges, or it forms a matching in the first 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
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.

The largest possible value of the Hosoya index, on a graph with vertices, is given by the complete graph . The Hosoya indices for the complete graphs are the telephone numbers

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

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

The Hosoya index is
#P-complete to compute, even for
planar graphs.^{
[5]} However, it may be calculated by evaluating the
matching polynomial *m _{G}* at the argument 1.

**^**Hosoya, Haruo (1971), "Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons",*Bulletin of the Chemical Society of Japan*,**44**(9): 2332–2339, doi: 10.1246/bcsj.44.2332.- ^
^{a}^{b}Hosoya, Haruo (2002), "The topological index*Z*before and after 1971",*Internet Electronic Journal of Molecular Design*,**1**(9): 428–442. **^**Internet Electronic Journal of Molecular Design, special issues dedicated to Professor Haruo Hosoya on the occasion of the 65th birthday: Volume 1 (2002), Number 9 — Volume 2 (2003), Number 6.**^**Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF),*Journal of Computational Biology*,**12**(7): 1004–1013, doi: 10.1089/cmb.2005.12.1004, PMID 16201918.**^**Jerrum, Mark (1987), "Two-dimensional monomer-dimer systems are computationally intractable",*Journal of Statistical Physics*,**48**(1): 121–134, Bibcode: 1987JSP....48..121J, doi: 10.1007/BF01010403, S2CID 189854401.**^**Gutman, Ivan (1991), "Polynomials in graph theory", in Bonchev, D.; Rouvray, D. H. (eds.),*Chemical Graph Theory: Introduction and Fundamentals*, Mathematical Chemistry, vol. 1, Taylor & Francis, pp. 133–176, ISBN 978-0-85626-454-2.**^**Courcelle, B.; Makowsky, J. A.; Rotics, U. (2001), "On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic" (PDF),*Discrete Applied Mathematics*,**108**(1–2): 23–52, doi: 10.1016/S0166-218X(00)00221-3.**^**Makowsky, J. A.; Rotics, Udi; Averbouch, Ilya; Godlin, Benny (2006), "Computing graph polynomials on graphs of bounded clique-width",*Proc. 32nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG '06)*(PDF), Lecture Notes in Computer Science, vol. 4271, Springer-Verlag, pp. 191–204, doi: 10.1007/11917496_18, ISBN 978-3-540-48381-6.**^**Jerrum, Mark; Sinclair, Alistair (1996), "Chapter 12: The Markov chain Monte Carlo method: an approach to approximate counting and integration",*Approximation Algorithms for NP-hard problems*(PDF), PWS Publishing, pp. 482–520

- Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors",
*Wiley-VCH*, ISBN 3-527-29913-0