On the extremal graphs with respect to the vertex PI index

The vertex Padmakar–Ivan (PI) index of a graph GG is the sum over all edges uv∈E(G)uv∈E(G) of the number of vertices which are not equidistant from uu and vv. We continue the research into estimating the extreme values of the PI index and answer the open question from [M.J. Nadjafi-Arani, G.H. Fath-Tabar, A.R. Ashrafi, Extremal graphs with respect to the vertex PI index, Appl. Math. Lett. 22 (2009) 1838–1840]. We prove that K⌊n/2⌋,⌈n/2⌉′, obtained from the complete bipartite graph K⌊n/2⌋,⌈n/2⌉K⌊n/2⌋,⌈n/2⌉ by adding one edge connecting two vertices from the class of size ⌈n/2⌉⌈n/2⌉, is the unique graph with the second-maximal value of PI index. We also determine the structure of the extremal graphs that have second-minimal PI index n(n−1)+2n(n−1)+2 among nn-vertex graphs. In addition, we calculated PI index for all graphs on ⩽10⩽10 vertices.