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.^[1] Mathematically, the invariant aggregates every independent-edge selection rather than only the size of a maximum matching.

If \(M_G(t)=\sum_k m_k(G)t^k\) is the matching generating polynomial under the positive-coefficient convention, then \(Z(G)=M_G(1)\). Sign-alternating “matching polynomial” conventions require an appropriate change of variables; merely substituting one without stating its normalization can give the wrong value.

The recognition invariant is finite graph + enumeration of all edge matchings by size + inclusion of the empty matching + summation/evaluation at one + isomorphism-invariant scalar.

Structural Signature¶

Graph carrier: finite simple graph unless another graph class is declared.
Matching: edge subset with no shared endpoints.
Cardinality strata: counts \(m_k(G)\) for all feasible \(k\).
Empty matching: mandatory contribution \(m_0=1\).
Total count: \(Z(G)=\sum_k m_k(G)\).
Generating relation: evaluation of the matching generating polynomial at one.
Deletion recurrence: partition matchings by whether they use a selected edge or vertex.
Component multiplicativity: disjoint components contribute independently, so their indices multiply.
Isomorphism invariance: relabeling vertices does not change the count.
Chemical interpretation: molecular graph used as a topological descriptor, not as a complete molecular model.

What It Is Not¶

It is not the matching number, which is the maximum cardinality of one matching. It is not the number of perfect matchings, not the number of maximum matchings, and not the count of nonempty matchings only. It is not the Hosoya polynomial commonly used for graph-distance distributions; similar naming masks a different invariant.

It is not the Wiener or Hyper-Wiener index, which aggregate vertex distances. Nor does equality of Hosoya indices imply graph isomorphism or chemical equivalence. A single integer necessarily collapses structural distinctions.

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.^[2]

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.

Polynomial conventions differ. Some authors write a generating polynomial with positive coefficients; others define the classical matching polynomial with alternating signs and vertex-degree exponents. A computation must state the exact polynomial before asserting an evaluation identity.^[3]

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.

The final compression sacrifices discrimination. Two nonisomorphic graphs can share \(Z\), and correlations with chemical properties can be confounded by size or graph class. The coefficient vector or additional descriptors may be needed when the scalar cannot separate candidates.

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.
Analyze complexity and use width-aware dynamic programming or approximation when necessary.
Treat descriptor–property associations as empirical claims requiring external validation.

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.^[4]

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.

Examples¶

Path recurrence. For a terminal edge, matchings either omit it or include it and omit its adjacent edge. With the base cases, indices of path graphs follow the Fibonacci recurrence.

Complete graph. Every choice of \(k\) disjoint vertex pairs is a matching; summing over \(k\) gives the telephone number for the vertex count.

Non-example. Reporting that a graph’s maximum matching has size four gives its matching number, not its Hosoya index.

Structural Tensions¶

Easy definition versus hard exact counting.
One-number compression versus graph discrimination.
Pure graph invariant versus empirical molecular interpretation.
Polynomial elegance versus normalization ambiguity.
General algorithms versus family-specific recurrences.
Unweighted topology versus chemically relevant labels and geometry.

Structural–Framed Character¶

The graph, matchings, cardinality counts, empty case, and total are structural. Molecular encoding, graph class, polynomial convention, approximation tolerance, and property interpretation are framed.

Structural Core vs. Domain Accent¶

The portable core is count-all-compatible-subsets. Edge incidence, graph matchings, matching polynomials, molecular graphs, and chemical topological descriptors are constitutive domain accent; the abstraction is domain-specific.

Matching is the proposed immediate parent through presupposition/composition. Measurement, Counting, Hyper-Wiener Index, matching polynomial, and independence polynomial are related but do not cover the invariant.

The prospective queue contains one strict edge to domain_specific:matching. No live DAG mutation is authorized.

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

Not to Be Confused With¶

Maximum matching size or matching number.
Number of perfect or maximum matchings.
Hosoya distance polynomial.
Wiener or Hyper-Wiener distance index.
A complete identifier for graph isomorphism.
A validated predictor of a chemical property without empirical study.

References¶

[1] Haruo Hosoya, “Topological Index. A Newly Proposed Quantity Characterizing the Topological Nature of Structural Isomers of Saturated Hydrocarbons,” Bulletin of the Chemical Society of Japan 44(9), 1971, 2332–2339. DOI 10.1246/bcsj.44.2332. registry ↩a ↩b

[2] Haruo Hosoya, “The Topological Index Z Before and After 1971,” Internet Electronic Journal of Molecular Design 1, 2002, 428–442. registry ↩

[3] Farrell Brualdi and Herbert Ryser, Combinatorial Matrix Theory, Cambridge University Press, 1991, discussions of matching enumeration and matching polynomials. registry ↩

[4] László Lovász and Michael D. Plummer, Matching Theory, North-Holland Mathematics Studies 121, 1986. registry ↩