![K4 matchings](https://upload.wikimedia.org/wikipedia/commons/7/7f/K4_matchings.svg)
The Hosoya index, also known as the Z index, of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is the total number of
matchings in it. The Hosoya index is always at least one, because the
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
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
is a Japanese people, Japanese chemist and emeritus professor of Ochanomizu University, Tokyo, Japan. He is the namesake of the Hosoya index used in discrete mathematics and computational chemistry.[topological index
In the fields of chemical graph theory, molecular topology, and mathematical chemistry, a topological index, also known as a connectivity index, is a type of a molecular descriptor that is calculated based on the molecular graph of a chemical compo ...]
in
chemical graph theory
Chemical graph theory is the topology branch of mathematical chemistry which applies graph theory to mathematical modelling of chemical phenomena.
The pioneers of chemical graph theory are Alexandru Balaban, Ante Graovac, Iván Gutman, Haruo Hosoy ...
.
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
s have the largest Hosoya index for any given number of vertices; their Hosoya indices are the
telephone numbers
A telephone number is a sequence of digits assigned to a landline telephone subscriber station connected to a telephone line or to a wireless electronic telephony device, such as a radio telephone or a mobile telephone, or to other devices f ...
.
History
This
graph invariant
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of discr ...
was introduced by
Haruo Hosoya
is a Japanese people, Japanese chemist and emeritus professor of Ochanomizu University, Tokyo, Japan. He is the namesake of the Hosoya index used in discrete mathematics and computational chemistry.[chemoinformatics
Cheminformatics (also known as chemoinformatics) refers to use of physical chemistry theory with computer and information science techniques—so called "''in silico''" techniques—in application to a range of descriptive and prescriptive proble ...]
for investigations of
organic compound
In chemistry, organic compounds are generally any chemical compounds that contain carbon-hydrogen or carbon-carbon bonds. Due to carbon's ability to catenate (form chains with other carbon atoms), millions of organic compounds are known. 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
The boiling point of a substance is the temperature at which the vapor pressure of a liquid equals the pressure surrounding the liquid and the liquid changes into a vapor.
The boiling point of a liquid varies depending upon the surrounding envir ...
s of
alkane
In organic chemistry, an alkane, or paraffin (a historical trivial name that also has other meanings), is an acyclic saturated hydrocarbon. In other words, an alkane consists of hydrogen and carbon atoms arranged in a tree structure in which ...
isomers
In chemistry, isomers are molecules or polyatomic ions with identical molecular formulae – that is, same number of atoms of each element – but distinct arrangements of atoms in space. Isomerism is existence or possibility of isomers.
Iso ...
and their Z indices, basing on his unpublished 1957 work carried out while he was an undergraduate student at the
University of Tokyo
, abbreviated as or UTokyo, is a public research university located in Bunkyō, Tokyo, Japan. Established in 1877, the university was the first Imperial University and is currently a Top Type university of the Top Global University Project by ...
.
[
]
Example
A linear alkane
In organic chemistry, an alkane, or paraffin (a historical trivial name that also has other meanings), is an acyclic saturated hydrocarbon. In other words, an alkane consists of hydrogen and carbon atoms arranged in a tree structure in which ...
, for the purposes of the Hosoya index, may be represented as a path graph
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
without any branching. A path with one vertex and no edges (corresponding to the methane
Methane ( , ) is a chemical compound with the chemical formula (one carbon atom bonded to four hydrogen atoms). It is a group-14 hydride, the simplest alkane, and the main constituent of natural gas. The relative abundance of methane on Eart ...
molecule) has one (empty) matching, so its Hosoya index is one; a path with one edge (ethane
Ethane ( , ) is an organic chemical compound with chemical formula . At standard temperature and pressure, ethane is a colorless, odorless gas. Like many hydrocarbons, ethane is isolated on an industrial scale from natural gas and as a petr ...
) has two matchings (one with zero edges and one with one edges), so its Hosoya index is two. Propane
Propane () is a three-carbon alkane with the molecular formula . It is a gas at standard temperature and pressure, but compressible to a transportable liquid. A by-product of natural gas processing and petroleum refining, it is commonly used a ...
(a length-two path) has three matchings: either of its edges, or the empty matching. ''n''-butane
Butane () or ''n''-butane is an alkane with the formula C4H10. Butane is a gas at room temperature and atmospheric pressure. Butane is a highly flammable, colorless, easily liquefied gas that quickly vaporizes at room temperature. The name but ...
(a length-three path) has five matchings, distinguishing it from isobutane
Isobutane, also known as ''i''-butane, 2-methylpropane or methylpropane, is a chemical compound with molecular formula HC(CH3)3. It is an isomer of butane. Isobutane is a colourless, odourless gas.
It is the simplest alkane with a tertiary carbon a ...
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 number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s, 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
In the mathematical field of graph theory, 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 ...
.
The largest possible value of the Hosoya index, on a graph with vertices, is given by the complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
. The Hosoya indices for the complete graphs are the telephone numbers
A telephone number is a sequence of digits assigned to a landline telephone subscriber station connected to a telephone line or to a wireless electronic telephony device, such as a radio telephone or a mobile telephone, or to other devices f ...
These numbers can be expressed by a summation
In mathematics, summation is the addition of a sequence of any kind of numbers, called ''addends'' or ''summands''; the result is their ''sum'' or ''total''. Beside numbers, other types of values can be summed as well: functions, vectors, mat ...
formula involving factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
s, as
Every graph that is not complete has a smaller Hosoya index than this upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an element ...
.
Algorithms
The Hosoya index is #P-complete to compute, even for planar 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. In other words, it can be drawn in such a way that no edges cross ...
s. However, it may be calculated by evaluating the matching polynomial In the mathematical fields of graph theory and combinatorics, a matching polynomial (sometimes called an acyclic polynomial) is a generating function of the numbers of matchings of various sizes in a graph. It is one of several graph polynomials ...
''mG'' at the argument 1. Based on this evaluation, the calculation of the Hosoya index is fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
for graphs of bounded treewidth
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
and polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
(with an exponent that depends linearly on the width) for graphs of bounded clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs.
It is defined as the minimum num ...
.
The Hosoya index can be efficiently approximated to any desired constant approximation ratio
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
using a fully-polynomial randomized approximation scheme.
Notes
References
*Roberto Todeschini, Viviana Consonni (2000) "Handbook of Molecular Descriptors", ''Wiley-VCH
Wiley-VCH is a German publisher owned by John Wiley & Sons. It was founded in 1921 as Verlag Chemie (meaning "Chemistry Press": VCH stands for ''Verlag Chemie'') by two German learned societies. Later, it was merged into the German Chemical Socie ...
'', {{ISBN, 3-527-29913-0
Graph invariants
Mathematical chemistry
Cheminformatics
Matching (graph theory)