Hosoya Polynomial for Subdivided Caterpillar Graphs

Abstract

Background: Computing Hosoya polynomial for a graph associated with a chemical compound plays a vital role in the field of chemistry. From Hosoya polynomial, it is easy to compute the Weiner index(Weiner number) and Hyper Weiner index of the underlying molecular structure. The Wiener number enables the identifying of three basic features of molecular topology: branching, cyclicity, and centricity (or centrality) and their specific patterns, which are well reflected by the physicochemical properties of chemical compounds. Caterpillar trees are used in chemical graph theory to represent the structure of benzenoid hydrocarbons molecules. In this representation, one forms a caterpillar in which each edge corresponds to a 6-carbon ring in the molecular structure, and two edges are incident at a vertex whenever the corresponding rings belong to a sequence of rings connected end-to-end in the structure. Due to the importance of Caterpillar trees, it is interesting to compute the Hosoya polynomial and the related indices.

Methods: The Hosoya polynomial of a graph G is defined as H(G;x) = Σ^d(G)_K=0 d(G.k)x^k. In order to compute the Hosoya polynomial, we need to find its coefficient d(G.k) which is the number of pairs of vertices of G which are at distance k. We classify the ordered pair of vertices which are at distance , 2 ≤ m ≤ (n + 1)k in the form of sets. Then finding the cardinality of these sets and adding them up will give us the value of coefficient d(G.m) . Finally, using the values of coefficients in the definition, we get the Hosoya polynomial of uniform subdivision of caterpillar graph.

Result: In this work, we compute the closed formula of Hosoya polynomial for subdivided caterpillar trees. This helps us to compute the Weiner index and hyper-Weiner index of uniform subdivision of caterpillar graph.

Conclusion: Caterpillar trees are among the important and general classes of trees. Thorn rods and thorn stars are the important subclasses of caterpillar trees. The idea of the present research article is to provide a road map to those researchers who are interested in studying the Hosoya polynomial for different trees.

Keywords: Hosoya polynomial; caterpillar graph; diameter.; hyper-wiener index; uniform subdivision; wiener index.