Researchers JVJ Vithiya Priya and KKK Karthika from the Department of Mathematics at the Vellore Institute of Technology have introduced a new computational framework that determines the Hosoya index of arbitrary simple connected graphs using matrix operations in MATLAB. Reporting in Frontiers in Chemistry, the mathematicians formulated an exact, non-recursive algorithm that bypasses the graph-specific case analyses and specialized recursive decompositions traditionally required to compute this topological descriptor. The Hosoya index, originally formulated in 1971 by Haruo Hosoya as the Z-index, represents a fundamental invariant in chemical graph theory defined as the total number of independent edge sets, or matchings, contained within a graph, including the empty set. Because the underlying problem of counting all valid matchings belongs to the computationally demanding complexity class of counting problems known as number-P-complete, mathematical chemists have historically relied on tailored recurrence relations, transfer-matrix formulations, or closed-form expressions restricted to narrow structural families. The newly published technique introduces an alternative linear-algebra approach that systematically constructs a binary enumeration matrix representing possible edge combinations and filters those combinations against an edge-adjacency matrix to extract the complete set of valid independent matchings.
The theoretical and practical significance of the Hosoya index stems from its demonstrated capacity to model the physicochemical and structural attributes of molecules directly from their topological graphs without necessitating laboratory experimentation. In his foundational 1971 investigations, Haruo Hosoya demonstrated an intrinsic correlation between calculated Z values and the experimentally observed boiling points of acyclic alkane isomers. Hosoya subsequently showed in 1973 that path graphs yield Hosoya indices that correspond exactly to the classical Fibonacci sequence. Over the ensuing decades, researchers established deeper theoretical relationships between the Hosoya index and complementary topological metrics, such as the Merrifield-Simmons index, while analyzing graph-theoretical bounds for trees, cycles, and specialized network topologies. In quantitative structure-property relationships and quantitative structure-activity relationships, the index functions as a whole-molecule descriptor reflecting molecular size, branching, and cyclicity. Despite its extensive analytical utility across drug discovery and materials science, calculating the Hosoya index directly from the Z-counting polynomial evaluated at unity rapidly becomes intractable as the number of vertices and edges increases, necessitating new algorithmic frameworks capable of handling diverse structural configurations.
Prior computational strategies designed to evaluate the Hosoya index have predominantly focused on limited topological categories where structural symmetries or acyclic backbones allow for simplified recursive calculations. Depth-first search algorithms and recursive dynamic programming formulations developed by earlier researchers achieved linear-time efficiency, but these techniques strictly required the target structure to be a tree or a unicyclic graph. Similarly, transfer-matrix and Hosoya-vector methods developed for catacondensed hexagonal systems, primitive coronoid systems, hollow hexagons, and pericondensed benzenoid systems depend heavily on linear arrangements of benzenoid rings with well-defined transfer states. Other specialized efforts yielded closed-form formulas tailored to specific synthetic topologies such as helm, gear, barbell, Dutch windmill, and friendship graphs, or dynamic programming bitmask formulations specifically tailored to fullerenes. However, each of these conventional frameworks demands that an entirely new recurrence or mathematical formula be established from scratch whenever a distinct graph family is examined. While edge-deletion and vertex-deletion identities allow for general graph computation, their recursive nature entails complex branching that the authors resolved through a unified, vectorized matrix pipeline.
The novel methodology operates by linking graph matchings to the structural properties of the line graph through a three-stage algorithmic pipeline. Formally, for a simple connected graph possessing an edge set of cardinality m, the algorithm constructs an m-by-m edge-adjacency matrix, which corresponds identically to the adjacency matrix of the line graph wherein vertices denote edges of the original graph and adjacencies signify shared endpoints. In the first phase, designated as Algorithm 1, the procedure generates a binary enumeration matrix whose columns represent all distinct combinations of selecting edges up to a theoretical matching limit. Because no independent edge set can contain more edges than half the total vertex count, the algorithm caps the maximum number of simultaneous ones in any column at the floor of n divided by two. By iterating from zero to this upper bound and applying standard combinatorial selection through the MATLAB command for calculating combinations, the routine systematically assembles candidate binary column vectors, yielding an overall time and space complexity of big-O of two to the power of m multiplied by m for the generation of this primary enumeration space.
Once the binary enumeration matrix has been assembled, the second stage, designated as Algorithm 2, filters out invalid edge subsets to isolate true matchings by exploiting quadratic forms in linear algebra. For every binary column vector extracted from the binary enumeration matrix, the algorithm performs a matrix-vector multiplication with the edge-adjacency matrix, followed by the inner product of the transposed binary vector with the resulting vector. If two or more selected edges in the candidate vector share a common vertex, the corresponding off-diagonal entries in the edge-adjacency matrix produce a strictly positive scalar value. Conversely, when the candidate edges are mutually independent, this quadratic product evaluates exactly to zero. By retaining solely those column vectors whose quadratic evaluation vanishes, the procedure constructs a filtered independence matrix representing the complete set of matchings. With p designating the total number of candidate columns, Algorithm 2 operates with a time complexity of big-O of p multiplied by m squared and a space complexity of big-O of p multiplied by m. Finally, Algorithm 3 determines the Hosoya index in constant big-O of one time simply by reading the number of columns in this independence matrix.
To confirm the mathematical accuracy and computational behavior of the matrix formulation, the authors executed extensive validation benchmarks across the homologous series of acyclic straight-chain alkanes, evaluating both hydrogen-suppressed graphs and complete molecular graphs including pendant hydrogens. In hydrogen-suppressed representations, carbon atoms constitute the vertices while covalent carbon-carbon bonds serve as edges, making the resulting graph isomorphic to a path graph. For these structures, spanning methane through decane, the calculated Hosoya indices exactly matched the Fibonacci progression: methane yielded 1, ethane produced 2, propane evaluated to 3, butane reached 5, pentane gave 8, hexane rose to 13, heptane climbed to 21, octane generated 34, nonane produced 55, and decane reached 89. Across this entire hydrogen-suppressed series, runtime measurements remained exceptionally low, shifting from 0.00013 seconds for methane to 0.0006 seconds for decane, with empirical growth ratios hovering near unity. This demonstrated that for small vertex counts, the computational overhead of the matrix procedure remains negligible when edge counts remain modest.
The authors contrasted these baseline observations by analyzing complete molecular graphs of the identical alkane molecules, where every individual hydrogen atom was explicitly integrated as a pendant vertex attached to its respective carbon center. In this complete structural representation, vertex counts increased markedly, ranging from 5 vertices in methane to 26 vertices in octane, significantly expanding the combinatorial matching space. Methane with hydrogens displayed a Hosoya index of 5 with an execution time of 0.0002 seconds, whereas octane exhibited an index of 22,013 and required 28.64 seconds of execution time. Intermediate molecules demonstrated steep growth in matching cardinality, with ethane yielding 17, propane generating 56, butane producing 185, pentane registering 611, hexane reaching 2,018, and heptane attaining 6,665. The positive slope of the fitted runtime curves plotted on logarithmic scales, alongside exponential curve fitting, illustrated that the computational cost of exact matching enumeration rises sharply as the presence of explicit hydrogen bonds increases the total edge count and broadens the combinatorial search field.
Expanding their validation beyond chemical molecules to biological structures, Priya and Karthika applied the matrix framework to thirteen distinct RNA secondary structure tree-graphs retrieved from the New York University RNA-As-Graphs database. In this convention, vertices denote structural secondary elements such as stems, loops, helices, or bulges rather than individual nucleotides, while edges capture topological adjacency between these components. Across RNA graphs ranging between two and six vertices, the MATLAB algorithm computed Hosoya indices spanning from 2 up to 13, consistently completing each evaluation in less than 0.00035 seconds. The empirical trials revealed that graphs possessing an identical number of vertices or edges did not exhibit identical execution runtimes; for instance, distinct six-vertex topologies required differing durations, confirming that the precise geometrical arrangement, vertex degrees, and interconnectivity of edges directly modulate the matching density and dictate the computational filtering workload.
The practical versatility of the algorithm was further verified on a structurally diverse collection of aromatic, fused-ring, and heteroatom-bearing organic molecules. Using unweighted graphs where each bond order was treated as a single edge, the authors computed the Hosoya index across varied compounds: phenol with 7 vertices produced an index of 26 in 0.0003 seconds; histamine with 8 vertices registered 43 in 0.0004 seconds; ethylbenzene with 8 vertices generated 44 in 0.0004 seconds; acetylcholine with 10 vertices yielded 51 in 0.0006 seconds; pentalene with 8 vertices reached 56 in 0.0007 seconds; naphthalene with 10 vertices produced 148 in 0.001 seconds; dopamine with 11 vertices achieved 151 in 0.001 seconds; adrenaline with 13 vertices gave 363 in 0.0033 seconds; caffeine with 14 vertices yielded 669 in 0.011 seconds; and melatonin with 17 vertices reached 3,198 in 0.08 seconds. Furthermore, comparative benchmark trials against recursive matching polynomial, transfer matrix, and linear tree techniques showed that while transfer-matrix methods were faster on regular chains, the proposed approach successfully computed complex topologies like complete graph K10 with 45 edges and index 9,496 in 0.075630 seconds, cycle graphs, pentacene, and the drug ramelteon. Strict boundary validations on edgeless graphs, isolated vertices, disconnected unions such as two disjoint edges with an isolated vertex, and star graphs confirmed that the algorithm handles disjoint components and over-estimated matching bounds without numerical error.
Notwithstanding its mathematical generality and non-recursive implementation, the authors detailed several clear limitations rooted in the inherent exponential scaling of exact combinatorial enumeration. Because total execution and memory complexities scale at big-O of two to the power of m multiplied by m squared, the framework experiences rapid memory consumption when constructing the high-dimensional binary enumeration matrix. The primary bottleneck is the column dimension p: while complete graph K10 with 45 edges was successfully processed because its five-matching ceiling limited the matrix columns to 1,385,980, the path graph P27 with 26 edges required 38,754,732 columns, illustrating that scalability is governed by the absolute column count rather than vertex or edge counts in isolation. All computational experiments were benchmarked within MATLAB R2026a running on an ASUS Vivobook equipped with an AMD Ryzen 3 7320U processor, 16 gigabytes of RAM, and Windows 11. To transcend these hardware boundaries in prospective research, the authors proposed implementing sparse matrix techniques, parallel and graphics-processing-unit acceleration, implementations in compiled high-performance languages, and hybrid heuristic approximation algorithms to extend matrix-based Hosoya index calculations to larger, highly dense networks.
Subject of Research: Matrix-based computation of the Hosoya index for general graphs in MATLAB
Article Title: Computing Hosoya index using an efficient matrix-based approach in MATLAB for general graphs
Article References: Vithiya Priya, J., & Karthika, K. (2026). Computing Hosoya index using an efficient matrix-based approach in MATLAB for general graphs. Frontiers in Chemistry, 14, 1919539. https://doi.org/10.3389/fchem.2026.1919539
Image Credits: AI Generated
DOI: 10.3389/fchem.2026.1919539
Keywords: Hosoya index, topological indices, chemical graph theory, MATLAB algorithm, binary enumeration matrix, edge adjacency matrix, independent edge sets, molecular graphs, RNA secondary structures, cheminformatics, computational complexity, line graph, Z-index, alkane isomers, combinatorial algorithms, graph matchings
News Source: Bethany Barker. (November 18, 2026). Mathematicians Design Matrix Method in MATLAB to Compute General Graph Hosoya Indices. Scienmag.



