Geodesic
Wiener and vertex PI indices of the strong product of graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 749-769.

Voir la notice de l'article provenant de la source Library of Science

The Wiener index of a connected graph G, denoted by W(G), is defined as ½ ∑_u,v ∈ V(G)d_G(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 ⊠ K_m₀,m₁,...,m_r -1, where K_m₀,m₁,...,m_r -1 is the complete multipartite graph with partite sets of sizes m₀,m₁, ...,m_r -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 
@article{DMGT_2012_32_4_a10,
     author = {Pattabiraman, K. and Paulraja, P.},
     title = {Wiener and vertex {PI} indices of the strong product of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {749--769},
     publisher = {mathdoc},
     volume = {32},
     number = {4},
     year = {2012},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a10/}
}
TY  - JOUR
AU  - Pattabiraman, K.
AU  - Paulraja, P.
TI  - Wiener and vertex PI indices of the strong product of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 749
EP  - 769
VL  - 32
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a10/
LA  - en
ID  - DMGT_2012_32_4_a10
ER  - 
%0 Journal Article
%A Pattabiraman, K.
%A Paulraja, P.
%T Wiener and vertex PI indices of the strong product of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 749-769
%V 32
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a10/
%G en
%F DMGT_2012_32_4_a10
Pattabiraman, K.; Paulraja, P. Wiener and vertex PI indices of the strong product of graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 4, pp. 749-769. http://geodesic.mathdoc.fr/item/DMGT_2012_32_4_a10/

[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.