Cacti with extremal PI Index

Document Type : Research Paper


1 Central China Normal University

2 University of Mississippi


The vertex PI index $PI(G) = \sum_{xy \in E(G)} [n_{xy}(x)‎ + ‎n_{xy}(y)]$ is a distance-based molecular structure descriptor‎, ‎where $n_{xy}(x)$ denotes the number of vertices which are closer to the vertex $x$ than to the vertex $y$ and which has been the considerable research in computational chemistry dating back to Harold Wiener in 1947‎. ‎A connected graph is a cactus if any two of its cycles have at most one common vertex‎. ‎In this paper‎, ‎we completely determine the extremal graphs with the greatest and smallest vertex PI indices mong all cacti with a fixed number of vertices‎. ‎As a consequence‎, ‎we obtain the sharp bounds with corresponding extremal cacti and extend a known result‎.


Main Subjects

[1] T. Al-Fozan, P. Manuel, I. Rajasingh and R. S. Rajan, Computing Szeged index of certain nanosheets using partition technique, MATCH Commun. Math. Comput. Chem., 72 (2014) 339–353.
[2] A. R. Ashrafi and A. Loghman, PI index of zig-zag polyhex nanotubes, MATCH Commun. Math. Comput. Chem., 55 (2006) 447–452.
[3] A. R. Ashrafi and A. Loghman, Padmakar-Ivan index of TUC4C8(S) nanotubes, J. Comput. Theor. Nanosci., 3 (2006) 378–381.
[4] A. R. Ashrafi and A. Loghman, PI index of armchair polyhex nanotubes, Ars Combin., 80 (2006) 193–199.
[5] A. R. Ashrafi, B. Manoochehrian and H. Yousefi-Azari, On the PI polynomial of a graph, Util. Math., 71 (2006) 97–108.
[6] A. R. Ashrafi and F. Rezaei, PI index of polyhex nanotori, MATCH Commun. Math. Comput. Chem., 57 (2007) 243–250.
[7] S. Chen, Cacti with the smallest, second smallest and third smallest Gutman index, J. Comb. Optim., 31 (2016) 327–332.
[8] A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math., 66 (2001) 211–249.
[9] A. A. Dobrynin, I. Gutman, S. Klavzzar and P. zZigert, Wiener index of hexagonal systems, Acta Appl. Math., 72 (2002) 247–294.
[10] K. C. Das and I. Gutman, Bound for vertex PI index in terms of simple graph parameters, Filomat, 27 (2013) 1583–1587.
[11] L. Feng and G. Yu, On the hyper-Wiener index of cacti, Util. Math., 93 (2014) 57–64.
[12] I. Gutman, S. Klavzar and B. Mohar, Fiftieth Anniversary of the Wiener Index, Discrete Appl. Math., 80 (1997) 1–113.
[13] M. Hoji, Z. Luo and E. Vumar, Wiener and vertex PI indices of Kronecker products of graphs, Discrete Appl. Math., 158 (2010) 1848–1855.
[14] A. Ilic and N. Milosavljevic, The weighted vertex PI index, Mathematical and Computer Modelling., 57 (2013) 623–631.
[15] S. Klavzar and I. Gutman, The Szeged and the Wiener Index of Graphs, Appl. Math. Lett., 9 (1996) 45–49.
[16] P. V. Khadikar, On a Novel Structural Descriptor PI, Nat. Acad. Sci. Lett., 23 (2000) 113–118.
[17] P. V. Khadikar, P. P. Kale, N. V. Deshpande, S. Karmarkar and V. K. Agrawal, Novel PI indices of hexagonal chains, J. Math. Chem., 29 (2001) 143–150.
[18] P. V. Khadikar, S. Karmarkar and R. G. Varma, The estimation of PI index of polyacenes, Acta Chim. Slov., 49 (2002) 755–771.
[19] 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.
[20] S. Li, H. Yang and Q. Zhao, Sharp bounds on Zagreb indices of cacti with $k$ pendant vertices, Filomat, 26 (2012) 1189–1200.
[21] K. Pattabiraman and P. Paulraja, Wiener and vertex PI indices of the strong product of graphs, Discuss. Math. Graph Theory, 32 (2012) 749–769.
[22] D. Wang and S. Tan, The maximum hyper-Wiener index of cacti, J. Appl. Math. Comput., 47 (2015) 91–102.
[23] H. Wang and L. Kang, On the Harary index of cacti, Util. Math., 96 (2015) 149–163.
[24] H. Wiener, Structural Determination of Paraffin Boiling Points, J. Am. Chem. Soc., 69 (1947) 17–20.
[25] S. Wang and B. Wei, Multiplicative Zagreb indices of cacti, Discrete Math. Algorithm. Appl.,
[26] S. Wang and B. Wei, Multiplicative Zagreb indices of $k$-trees, Discrete Appl. Math., 180 (2015) 168–175.