Generic placeholder image

Combinatorial Chemistry & High Throughput Screening

Author(s): Muhammad Numan, Aamra Nawaz, Adnan Aslam* and Saad Ihsan Butt

DOI: 10.2174/1386207323666201211094406

DownloadDownload PDF Flyer Cite As
Hosoya Polynomial for Subdivided Caterpillar Graphs

Page: [554 - 559] Pages: 6

  • * (Excluding Mailing and Handling)

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)xk. 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, wiener index, hyper-wiener index, caterpillar graph, uniform subdivision, diameter.

Graphical Abstract

[1]
Hosoya, H. On some counting polynomials in chemistry. Discrete Appl. Math., 1988, 19, 239-257.
[http://dx.doi.org/10.1016/0166-218X(88)90017-0]
[2]
Sagan, B.E.; Yeh, Y.N.; Zhang, P. The Wiener polynomial of a graph. Int. J. Quantum Chem., 1996, 60, 959-969.
[http://dx.doi.org/10.1002/(SICI)1097-461X(1996)60:5<959:AID-QUA2>3.0.CO;2-W]
[3]
Caporossi, G.; Dobrynin, A.A.; Gutman, I.; Hansen, P. Trees with palindromic Hosoya polynomials. Graph Theory Notes New York., 1999, 37, 10-16.
[4]
Gutman, I. Some relations between distance based polynomials of trees. Bull. Acad. Serbe Sci. Arts (Cl. Sci. Math. Natur.),, 2005, 131, 1-7.
[5]
Gutman, I.; Klavzar, S.; Petkovsek, M.; Zigert, P. On Hosoya polynomials of benzenoid graphs. MATCH Commun. Math. Comput. Chem., 2001, 43, 49-66.
[6]
Xu, S.; Zhang, H.H. The Hosoya polynomial decomposition for catacon densed benzenoid graphs. Discrete Appl. Math., 2008, 156, 2930-2938.
[http://dx.doi.org/10.1016/j.dam.2007.12.004]
[7]
Stevanovic, D. Hosoya polynomial of composite graphs. Discrete Math., 2001, 235, 237-244.
[http://dx.doi.org/10.1016/S0012-365X(00)00277-6]
[8]
Doslic, T. Vertex weighted Wiener polynomials for composite graphs. Ars Math. Contemp., 2008, 1, 66-80.
[http://dx.doi.org/10.26493/1855-3974.15.895]
[9]
Eliasi, M.; Iranmanesh, A. Hosoya polynomial of hierarchical product of graphs. MATCH Commun. Math. Comput. Chem., 2013, 69, 111-119.
[10]
Xu, S.; Zhang, H.; Diudea, M.V. Hosoya polynomials of zigzag openended nanotubes. MATCH Commun. Math. Comput. Chem., 2007, 57, 443-456.
[11]
Xu, S.; Zhang, H. Hosoya polynomials of armchair openended nanotubes. Int. J. Quantum Chem., 2007, 107, 586-596.
[http://dx.doi.org/10.1002/qua.21161]
[12]
Xu, S.; Zhang, H. Hosoya polynomials of TUC4C8(S) nanotubes. J. Math. Chem., 2009, 45, 488-502.
[http://dx.doi.org/10.1007/s10910-008-9422-3]
[13]
Diudea, M.V. Hosoya polynomial in tori. MATCH Commun. Math. Comput. Chem., 2002, 45, 109-122.
[14]
Yan, W.; Yang, B.Y.; Yeh, Y.N. The behavior of Wiener indices and polynomials of graphs under ve graph decorations. Appl. Math. Lett., 2007, 20, 290-295.
[http://dx.doi.org/10.1016/j.aml.2006.04.010]
[15]
Eliasi, M.; Taeri, B. Hosoya polynomial of zigzag polyhex nanotorus. J. Serb. Chem. Soc., 2008, 73, 311-319.
[http://dx.doi.org/10.2298/JSC0803311E]
[16]
Ali, A.A.; Ali, A.M. Hosoya polynomials of pentachains. MATCH Commun. Math. Comput. Chem., 2011, 65, 807-819.
[17]
Lin, X.; Xu, S.J.; Yeh, Y.N. Hosoya polynomials of circumcoronene series. MATCH Commun. Math. Comput. Chem., 2013, 69, 755-763.
[18]
Li, X.; Wang, G.; Bian, H.; Hu, R. The Hosoya polynomial decomposition for polyphenyl chains. MATCH Commun. Math. Comput. Chem., 2012, 67, 357-368.
[19]
Klavzar, S.; Mollard, M. Wiener index and Hosoya polynomial of Fibonacci and Lucas cubes. MATCH Commun. Math. Comput. Chem., 2012, 68, 311-324.
[20]
Narayankar, P.K.; Lokesh, S.B.; Mathad, V.; Gutman, I. Hosoya polynomial of Hanoi graphs. Kragujevac J. Math., 2012, 36, 51-57.
[21]
Behmaram, A. Youse_Azari, H.; Ashra, A.R. Some new results on distance based polynomials. MATCH Commun. Math. Comput. Chem., 2011, 65, 39-50.
[22]
Gutman, I.; Miljkovic, O.; Zhou, B.; Petrovic, M. Inequalities between distance based graph polynomials. Bull. Acad. Serbe Sci. Arts (Cl. Sci. Math. Natur.),, 2006, 133, 57-68.
[23]
Mihalic, Z.; Trinajstic, N. A graph theoretical approach to structure property relationships. J. Chem. Educ., 1992, 69, 701-712.
[http://dx.doi.org/10.1021/ed069p701]
[24]
Gutman, I.; Yeh, Y.N.; Lee, S.L.; Luo, Y.L. Some recent results in the theory of the Wiener number. Indian J. Chem., 1993, 32(A), 651-661.
[25]
Gutman, I.; Potgieter, J.H. Wiener index and intermolecular forces. J. Serb. Chem. Soc., 1997, 62, 185-192.
[26]
Rouvray, D.H. The rich legacy of half century of the Wiener indexRouvray, D.H; King (Eds.), R.B., Topology in Chemistry | Discrete Mathematics of Molecules, Horwood, Chichester; , 2002; pp. 16-37.
[27]
Dobrynin, A.A.; Entringer, R.; Gutman, I. Wiener index of trees theory and applications. Acta Appl. Math., 2001, 66, 211-249.
[http://dx.doi.org/10.1023/A:1010767517079]
[28]
mDobrynin, A.A.; Gutman, I.; Klavzar, S.; Zigert, P. Wiener index of hexagonal systems. Acta Appl. Math., 2002, 72, 247-294.
[http://dx.doi.org/10.1023/A:1016290123303]
[29]
Schultz, H.P. Topological organic chemistry. 1. Graph theory and topological indices of alkanes. J. Chem. Inf. Comput. Sci., 1989, 29, 227-228.
[http://dx.doi.org/10.1021/ci00063a012]
[30]
Gutman, I. Selected properties of the Schultz molecular topological index. J. Chem. Inf. Comput. Sci., 1994, 34, 1087-1089.
[http://dx.doi.org/10.1021/ci00021a009]
[31]
Klein, D.J.; Mihalic, Z.; Plavsic, D.; Trinajstic, N. Molecular topological index: A relation with the Wiener index. J. Chem. Inf. Comput. Sci., 1992, 32, 304-305.
[http://dx.doi.org/10.1021/ci00008a008]