Hosoya Index¶

Count every matching of a graph, including the empty matching, to obtain a graph invariant used in matching theory and as a molecular topological descriptor.

Version: v3 · 2026-09-19 · History
Domain-specific #: 2021
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Chemical Graph Theory → Mathematics
Aliases: Z index, Hosoya Z-index, Topological index Z

Core Idea¶

The Hosoya index of a finite graph \(G\), conventionally written \(Z(G)\), is the total number of its matchings, including the empty matching. If \(m_k(G)\) is the number of matchings containing exactly \(k\) pairwise nonincident edges, then

\[ Z(G)=\sum_{k\ge 0}m_k(G),\qquad m_0(G)=1. \]

Hosoya introduced the quantity in chemical graph theory to characterize the carbon-skeleton topology of saturated hydrocarbons and observed relationships with molecular branching, ring closure, and physical properties. Mathematically, the invariant aggregates every independent-edge selection rather than only the size of a maximum matching.

How would you explain it like I'm…

Counting Partner Picks

Draw some dots and connect some of them with sticks. Now pick sticks, but no dot can touch two picked sticks. Count every way you could pick them, even picking no sticks at all. That number is the Hosoya index.

Counting All Matchings

A graph is a set of dots joined by lines. A matching is a choice of lines where no two chosen lines share a dot, like pairing up friends so nobody is in two pairs. The Hosoya index counts every possible matching: ones with one line, ones with two lines, and so on. It also counts the empty choice, where you pick no lines. Chemists first used it to describe the shapes of molecules.

Total Matching Count

In a graph, a matching is a set of edges where no two edges share a vertex. The Hosoya index Z(G) is the total number of matchings of a finite graph G. You add up the matchings of every size k, and the empty matching counts as 1. This is different from asking for the largest matching, which only looks at the maximum size. The Hosoya index counts all of them. Hosoya introduced it in chemistry to describe the carbon skeletons of saturated hydrocarbons. It relates to how branched a molecule is, whether it has rings, and some of its physical properties.

For a finite graph G, let m_k(G) be the number of matchings with exactly k pairwise nonincident edges, with m_0 = 1. The Hosoya index is Z(G) = Σ_k m_k(G), the total count of matchings including the empty one. It is a graph invariant: isomorphic graphs have the same value. It aggregates every independent-edge selection, rather than recording only the matching number. Under the positive-coefficient matching generating polynomial M_G(t) = Σ m_k t^k, we have Z(G) = M_G(1). With the sign-alternating matching polynomial, you need a stated change of variables to recover Z, and naive substitution gives wrong values. Hosoya introduced it in chemical graph theory to encode hydrocarbon skeleton topology. He observed correlations with branching, ring closure and physical properties.

Scope of Application¶

The invariant is used in enumerative graph theory, matching theory, chemical graph theory, molecular-descriptor studies, recurrence analysis, and algorithmic complexity. For paths, the deletion recurrence yields Fibonacci numbers; for complete graphs it yields involution/telephone numbers. Tree and unicyclic families support specialized formulas and extremal questions.

Exact computation on unrestricted graphs is a counting problem with #P-level difficulty, while bounded structural width, recurrence, dynamic programming, or randomized approximation can make useful classes tractable. Chemical applications require a declared molecular-graph convention, treatment of hydrogens and bond types, and validation against the target property.

Clarity¶

Every set of nonincident edges counts once, including the set with no edges. For a path on four vertices, the matchings are: empty; each of the three singleton edges; and the pair of the two outer edges. Hence \(Z=5\). This example also prevents the common error of counting matched vertices rather than edge subsets.

Manages Complexity¶

Cardinality counts compress an exponential family of edge subsets into a short coefficient sequence, and the final index compresses that sequence to one scalar. Deletion recurrences factor the problem into smaller graphs: matchings either avoid a chosen edge or include it and thereby exclude adjacent choices.

Abstract Reasoning¶

Define the graph and any chemical encoding convention.
Confirm whether loops, multiple edges, weights, or labels are excluded or specially handled.
Partition edge subsets by matching cardinality.
Include the empty matching explicitly.
Enumerate directly for small graphs or apply deletion/component recurrences.
Cross-check with a correctly normalized matching generating polynomial.
Verify invariance under relabeling and test base cases.

Knowledge Transfer¶

The transferable pattern is to characterize a structure by counting all mutually compatible subconfigurations. Independence polynomials, matching partition functions, and statistical-mechanical monomer–dimer models share this logic.

The proposed immediate parent is Matching through presupposition/composition: every counted object is a matching, while the Hosoya index is the aggregate invariant derived from the full matching family.

Relationships to Other Abstractions¶

Current abstraction Hosoya Index Domain-specific

Parents (1) — outgoing typed relations

Hosoya Index is a kind of Matching Domain-specific

Matching is the broader abstraction this entry instantiates through presupposition/composition.

Hierarchy paths (3) — routes to 3 parentless roots

Hosoya Index → is a kind of Matching → is a kind of, typical Optimization

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Hosoya Index sits in a moderately populated region (42^nd percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Graph Classes & Invariants (40 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25