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 ...

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

, 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

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. 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

n

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 ...

K_n

. The Hosoya indices for the complete graphs are the

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

\sum_^ \frac.

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 ...

''m_G'' 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)