Submit Manuscript  

Article Details

Hosoya Polynomial for Subdivided Caterpillar Graphs


Muhammad Numan, Aamra Nawaz, Adnan Aslam* and Saad Ihsan Butt  


Background: Computing Hosoya polynomial for the graph associated with the chemical compound plays a vital role in the field of chemistry. From Hosoya polynomial, it is easy to compute 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 have been 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.

Method: The Hosoya polynomial of a graph G is defined as H(G;x)=∑_(k=0)d(G) d(G,k) x^k . In order to compute the Hosoya polynomial, we need to find its coefficients d(G,k) which is the number of pair of vertices of G which are at distance k. We classify the ordered pair of vertices which are at distance m,2≤m≤(n+1)k in the form of sets. Then finding the cardinality of these sets and adding 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 one of the important and general classes of trees. Thorn rods and thorn stars are the important subclasses of caterpillar trees. The ideas of the present research article is to give a road map to those researchers who are interesting to study the Hosoya polynomial for different trees.


Hosoya polynomial, Wiener index, hyper-Wiener index, caterpillar graph, uniform subdivision, Diameter.


Department of Mathematics, COMSATS University Islamabad Attock Campus , Attock, Department of Mathematics, COMSATS University Islamabad Attock Campus , Attock, Department of Natural Sciences and Humanities, University of Engineering and Technology, Lahore, Department of Mathematics, COMSATS University Islamabad Lahore Campus , Lahore

Full Text Inquiry