Hosoya index
Encyclopedia
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.
in 1971. It is often used in chemoinformatics for investigations of organic compound
s.
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 point
s 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
.
, 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 number
s. Ths structure of the matchings in these graphs may be visualized using a Fibonacci cube
.
s. However, it may be calculated by evaluating the matching polynomial
mG at the argument 1. Based on this evaluation, the calculation of the Hosoya index is fixed-parameter tractable for graphs of bounded treewidth and polynomial (with an exponent that depends linearly on the width) for graphs of bounded clique-width
.
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
is the total number of matchings in it. The Hosoya index is always at least one, because the empty set
Empty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
of edges is counted as a matching for this purpose. Equivalently, the Hosoya index is the number of non-empty matchings plus one.
History
This graph invariant was introduced by Haruo HosoyaHaruo Hosoya
is a Japanese chemist, emeritus professor of the Ochanomizu University, Tokyo, Japan, the namesake of the Hosoya index used in computational chemistry....
in 1971. It is often used in chemoinformatics for investigations of organic compound
Organic compound
An organic compound is any member of a large class of gaseous, liquid, or solid chemical compounds whose molecules contain carbon. For historical reasons discussed below, a few types of carbon-containing compounds such as carbides, carbonates, simple oxides of carbon, and cyanides, as well as the...
s.
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 point
Boiling point
The boiling point of an element or a substance is the temperature at which the vapor pressure of the liquid equals the environmental pressure surrounding the liquid....
s of alkane
Alkane
Alkanes are chemical compounds that consist only of hydrogen and carbon atoms and are bonded exclusively by single bonds without any cycles...
isomers and their Z indices, basing on his unpublished 1957 work carried out while he was an undergraduate student at the University of Tokyo
University of Tokyo
, abbreviated as , is a major research university located in Tokyo, Japan. The University has 10 faculties with a total of around 30,000 students, 2,100 of whom are foreign. Its five campuses are in Hongō, Komaba, Kashiwa, Shirokane and Nakano. It is considered to be the most prestigious university...
.
Example
A linear alkaneAlkane
Alkanes are chemical compounds that consist only of hydrogen and carbon atoms and are bonded exclusively by single bonds without any cycles...
, for the purposes of the Hosoya index, may be represented as a path graph
Path graph
In the mathematical field of graph theory, a path graph or linear graph is a particularly simple example of a tree, namely a tree with two or more vertices that is not branched at all, that is, contains only vertices of degree 2 and 1...
without any branching. A path with one vertex and no edges (corresponding to the methane
Methane
Methane is a chemical compound with the chemical formula . It is the simplest alkane, the principal component of natural gas, and probably the most abundant organic compound on earth. The relative abundance of methane makes it an attractive fuel...
molecule) has one (empty) matching, so its Hosoya index is one; a path with one edge (ethane
Ethane
Ethane is a chemical compound with chemical formula C2H6. It is the only two-carbon alkane that is an aliphatic hydrocarbon. At standard temperature and pressure, ethane is a colorless, odorless gas....
) has two matchings (one with zero edges and one with one edges), so its Hosoya index is two. Propane
Propane
Propane is a three-carbon alkane with the molecular formula , normally a gas, but compressible to a transportable liquid. A by-product of natural gas processing and petroleum refining, it is commonly used as a fuel for engines, oxy-gas torches, barbecues, portable stoves, and residential central...
(a length-two path) has three matchings: either of its edges, or the empty matching. n-butane
Butane
Butane is a gas with the formula C4H10 that is an alkane with four carbon atoms. The term may refer to any of two structural isomers, or to a mixture of them: in the IUPAC nomenclature, however, butane refers only to the unbranched n-butane isomer; the other one being called "methylpropane" or...
(a length-three path) has five matchings, distinguishing it from isobutane
Isobutane
Isobutane, also known as methylpropane, is an isomer of butane. It is the simplest alkane with a tertiary carbon. Concerns with depletion of the ozone layer by freon gases have led to increased use of isobutane as a gas for refrigeration systems, especially in domestic refrigerators and freezers,...
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 number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
s. Ths structure of the matchings in these graphs may be visualized using a Fibonacci cube
Fibonacci cube
The Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in Number Theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices, studied in graph-theoretic mathematics...
.
Algorithms
The Hosoya index is #P-complete to compute, even for planar graphPlanar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s. However, it may be calculated by evaluating the matching polynomial
Matching polynomial
In graph theory and combinatorics, both fields within mathematics, a matching polynomial is a generating function of the numbers of matchings of various sizes in a graph.-Definition:...
mG at the argument 1. Based on this evaluation, the calculation of the Hosoya index is fixed-parameter tractable for graphs of bounded treewidth and polynomial (with an exponent that depends linearly on the width) for graphs of bounded clique-width
Clique-width
In graph theory, the clique-width of a graph G is the minimum number of labels needed to construct G by means of the following 4 operations :#Creation of a new vertex v with label i...
.