Download PDF - Wiener and vertex PI indices of the strong product of graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

Wiener and vertex PI indices of the strong product of graphs

Authors 1, 1

Affiliations

  1. 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)d²G(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⊠Km₀,m₁,...,mr-1, where Km₀,m₁,...,mr-1 is the complete multipartite graph with partite sets of sizes m₀,m₁,...,mr-1, are obtained. Also lower bounds for Wiener and hyper-Wiener indices of strong product of graphs are established.

Keywords

ENG
strong product, Wiener index, hyper-Wiener index, vertex PI index

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2012/32/4
Export to PBN, Opens in new tab
Pages:
749-769
Main language of publication
English
Received
2011-06-20
Accepted
2012-01-25
Published
2012

DOI: 10.7151/dmgt.1647

Exact and natural sciences