Wiener and vertex PI indices of the strong product of graphs

K. Pattabiraman; P. Paulraja

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 4, page 749-769
  • ISSN: 2083-5892

Abstract

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

How to cite

top

K. Pattabiraman, and P. Paulraja. "Wiener and vertex PI indices of the strong product of graphs." Discussiones Mathematicae Graph Theory 32.4 (2012): 749-769. <http://eudml.org/doc/270865>.

@article{K2012,
abstract = {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.},
author = {K. Pattabiraman, P. Paulraja},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {strong product; Wiener index; hyper-Wiener index; vertex PI index},
language = {eng},
number = {4},
pages = {749-769},
title = {Wiener and vertex PI indices of the strong product of graphs},
url = {http://eudml.org/doc/270865},
volume = {32},
year = {2012},
}

TY - JOUR
AU - K. Pattabiraman
AU - P. Paulraja
TI - Wiener and vertex PI indices of the strong product of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 749
EP - 769
AB - 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.
LA - eng
KW - strong product; Wiener index; hyper-Wiener index; vertex PI index
UR - http://eudml.org/doc/270865
ER -

References

top
  1. [1] A.R. Ashrafi and A. Loghman, PI index of zig-zag polyhex nanotubes, MATCH Commun. Math. Comput. Chem. 55 (2006) 447-452. Zbl1104.05023
  2. [2] A.R. Ashrafi and F. Rezaei, PI index of polyhex nanotori, MATCH Commun. Math. Comput. Chem. 57 (2007) 243-250. Zbl1193.92085
  3. [3] A.R. Ashrafiand and A. Loghman, PI index of armchair polyhex nanotubes, Ars Combin. 80 (2006) 193-199. Zbl1174.05496
  4. [4] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory ( Springer-Verlag, New York, 2000). Zbl0938.05001
  5. [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. Zbl1110.92059
  6. [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. Zbl0982.05044
  7. [7] I. Gutman and O.E. Polansky, Mathematical Concepts in Organic Chemistry ( Springer-Verlag, Berlin, 1986). Zbl0657.92024
  8. [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. Zbl1208.05124
  9. [9] W. Imrich and S. Klavžar, Product graphs: Structure and Recognition ( John Wiley, New York, 2000). Zbl0963.05002
  10. [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). Zbl1156.05001
  11. [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. [12] P.V. Khadikar, On a novel structural descriptor PI, Nat. Acad. Sci. Lett. 23 (2000) 113-118. 
  13. [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. Zbl1155.05316
  14. [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. Zbl1152.05323
  15. [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. Zbl1034.92040
  16. [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. [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. [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. [19] I. Lukovits, QSPR/QSAR Studies by Molecular Descriptors, (Nova, Huntington, M.V. Diudea (Ed.), 2001) p.31. 
  20. [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. [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. Zbl1255.05065
  22. [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. Zbl1241.05121
  23. [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. Zbl1242.05232
  24. [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. [25] R. Todeschini and V. Consonni, Handbook of Molecular Descriptors (Wiley-VCH, Weinheim, 2000). 
  26. [26] H. Wiener, Structural determination of the paraffin boiling points, J. Amer. Chem. Soc. 69 (1947) 17-20, doi: 10.1021/ja01193a005. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.