DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 32(4) (2012) 749-769
DOI: 10.7151/dmgt.1647

Wiener and Vertex PI Indices of the Strong Product of Graphs

K. Pattabiraman and P. Paulraja

Department of Mathematics, Annamalai University
Annamalainagar 608 002, India

Abstract

The Wiener index of a connected graph G, denoted by W(G), is defined as ½ ∑u,v ∈ V(G)dG(u,v). Similarly, the hyper-Wiener index of a connected graph G, denoted by WW(G), is defined as ½W(G)+¼ ∑u,v ∈ V(G)d2G(u,v). The vertex Padmakar-Ivan (vertex PI) index of a graph G is the sum over all edges uv of G of the number of vertices which are not equidistant from u and v. In this paper, the exact formulae for Wiener, hyper-Wiener and vertex PI indices of the strong product G⊠ Km0,m1, …,mr −1, where Km0,m1, …,mr −1 is the complete multipartite graph with partite sets of sizes m0,m1, …,mr −1, are obtained. Also lower bounds for Wiener and hyper-Wiener indices of strong product of graphs are established.

Keywords: strong product, Wiener index, hyper-Wiener index, vertex PI index

2010 Mathematics Subject Classification: 05C12, 05C76.

References

[1]A.R. Ashrafi and A. Loghman, PI index of zig-zag polyhex nanotubes, MATCH Commun. Math. Comput. Chem. 55 (2006) 447--452.
[2]A.R. Ashrafi and F. Rezaei, PI index of polyhex nanotori, MATCH Commun. Math. Comput. Chem. 57 (2007) 243--250.
[3]A.R. Ashrafiand and A. Loghman, PI index of armchair polyhex nanotubes, Ars Combin. 80 (2006) 193--199.
[4]R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory ( Springer-Verlag, New York, 2000).
[5]H. Deng, S. Chen and J. Zhang, The PI index of phenylenes, J. Math. Chem. 41 (2007) 63--69, doi: 10.1007/s10910-006-9198-2.
[6]A.A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math. 66 (2001) 211--249, doi: 10.1023/A:1010767517079.
[7]I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry ( Springer-Verlag, Berlin, 1986).
[8]M. Hoji, Z. Luo and E. Vumar, Wiener and vertex PI indices of Kronecker products of graphs, Discrete Appl. Math. 158 (2010) 1848--1855, doi: 10.1016/j.dam.2010.06.009.
[9]W. Imrich and S. Klavžar, Product graphs: Structure and Recognition ( John Wiley, New York, 2000).
[10]W. Imrich, S. Klavžar and D. F. Rall, Topics in Graph Theory: Graphs and Their Cartesian Product ( AK Peters Ltd., Wellesley, Massachusetts, 2008).
[11]P.V. Khadikar, S. Karmarkar and V.K. Agrawal, A novel PI index and its application to QSPR/QSAR studies, J. Chem. Inf. Comput. Sci. 41 (2001) 934--949, doi: 10.1021/ci0003092.
[12]P.V. Khadikar, On a novel structural descriptor PI, Nat. Acad. Sci. Lett. 23 (2000) 113--118.
[13]M.H. Khalifeh, H. Yousefi-Azari and A.R. Ashrafi, The hyper-Wiener index of graph operations, Comput. Math. Appl. 56 (2008) 1402--1407, doi: 10.1016/j.camwa.2008.03.003.
[14]M.H. Khalifeh, H. Yousefi-Azari and A.R. Ashrafi, Vertex and edge PI indices of cartesian product graphs, Discrete Appl. Math. 156 (2008) 1780--1789, doi: 10.1016/j.dam.2007.08.041 .
[15]S. Klavžar, P. Zigert and I. Gutman, An algorithm for the calculation of the hyper-Wiener index of benzenoid hydrocarbons, Comput. Chem. 24 (2000) 229--233, doi: 10.1016/S0097-8485(99)00062-5 .
[16]D.J. Klein, I. Lukovits and I. Gutman, On the definition of the hyper-Wiener index for cycle-containing structures, J. Chem. Inf. Comput. Sci. 35 (1995) 50--52, doi: 10.1021/ci00023a007.
[17]W. Linert, F. Renz, K. Kleestorfer and I. Lukovits, An algorithm for the computation of the hyper-Winer index for the characterization and discrimination of branched acyclic molecules, Comput. Chem. 19 (1995) 395--401, doi: 10.1016/0097-8485(95)00048-W.
[18]I. Lukovits, A Note on a formula for the hyper-Wiener index of some trees, J. Chem. Inf. Comput. Sci. 34 (1994) 1079--1081, doi: 10.1021/ci00021a007.
[19]I. Lukovits, QSPR/QSAR Studies by Molecular Descriptors, (Nova, Huntington, M.V. Diudea (Ed.), 2001) p.31.
[20]D.E. Needham, I.C. Wei and P.G. Seybold, Molecular modeling of the physical properties of alkanes, J. Amer. Chem. Soc. 110 (1988) 4186--4194, doi: 10.1021/ja00221a015.
[21]K. Pattabiraman and P. Paulraja, Wiener index of the tensor product of a path and a cycle, Discuss. Math. Graph Theory 31 (2011) 737--751, doi: 10.7151/dmgt.1576.
[22]K. Pattabiraman and P. Paulraja, On some topological indices of the tensor products of graphs, Discrete Appl. Math. 160 (2012) 267-279, doi: 10.1016/j.dam.2011.10.020 .
[23]K. Pattabiraman and P. Paulraja, Vertex and edge Padmakar-Ivan indices of the generalized hierarchical product of graphs, Discrete Appl. Math. 160 (2012) 1376--1384, doi: 10.1016/j.dam.2012.01.021.
[24]M. Randi'c, Novel molecular descriptor for structure-property studies, Chem. Phys. Lett. 211 (1993) 478--483, doi: 10.1016/0009-2614(93)87094-J.
[25]R. Todeschini and V. Consonni, Handbook of Molecular Descriptors (Wiley-VCH, Weinheim, 2000).
[26]H. Wiener, Structural determination of the paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17--20, doi: 10.1021/ja01193a005.

Received 20 June 2011
Revised 25 January 2012
Accepted 27 January 2012