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: v2 · 2026-09-06 · History
Domain-specific #: 2021
Origin domain: mathematics
Subdomain: chemical graph theory
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.

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. 2. Confirm whether loops, multiple edges, weights, or labels are excluded or specially handled. 3. Partition edge subsets by matching cardinality. 4. Include the empty matching explicitly. 5. Enumerate directly for small graphs or apply deletion/component recurrences. 6. Cross-check with a correctly normalized matching generating polynomial. 7. 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) — more general patterns this builds on

Hosoya Index is a kind of Matching Domain-specific

Matching is the proposed immediate parent through presupposition/composition.

Hierarchy paths (3) — routes to 3 parentless roots

Hosoya Index → Matching → Optimization

Show alternative paths (2)

Neighborhood in Abstraction Space¶

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

Family — Graph Coloring & Labeling (14 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-09-08