Graph Invariants of Deleted Lexicographic Product of Graphs

Document Type : Original Scientific Paper


‎Department of Applied Mathematics, ‎Faculty of Mathematical Sciences‎, ‎‎Ferdowsi University of Mashhad, ‎Mashhad‎, ‎I‎. ‎R‎. ‎Iran


‎The deleted lexicographic‎ ‎product G[H]-nG of graphs G and H is a graph with vertex set V(G)×V(H)‎ and u=(u1‎, ‎v1) is adjacent with v=(u2‎, ‎v2) whenever (u1=u2 and‎ v1 is adjacent with v2) or (v1 ≠ v2 and u1 is adjacent with u2)‎. ‎In this paper‎, ‎we compute the exact values of the Wiener‎, ‎vertex PI and Zagreb indices‎ of deleted lexicographic product of graphs‎. ‎Applications of our results under some examples are presented‎.


[1] A. R. Ashrafi, A. Karbasioun and M. V. Diudea, Computing Wiener and detour indices of a new type of nanostar dendrimers, MATCH Commun. Math. Comput. Chem. 65 (2011) 193 - 200.
[2] M. V. Diudea, Polyhex Tori Originating in Square Tiled Tori, In: M. V. Diudea (Ed.), Nanostructures: Novel Architecture, Nova Science Publishers, New York, 2005, 111 - 126.
[3] M. V. Diudea, M. Stefu, B. Pârv and P. E. John, Wiener index of armchair polyhex nanotubes, Croat. Chem. Acta 77 (2004) 111 - 115.
[4] M. V. Diudea and I. Gutman, Wiener-type topological indices, Croat. Chem. Acta 71 (1998) 21 - 51.
[5] J. Feigenbaum and A. A. Schäffer, Recognizing composite graphs is equivalent to testing graph isomorphism, SIAM J. Comput. 15 (1986) 619 - 627.
[6] B. Frelih and Š. Miklavic, Edge regular graph products, Electron. J. Combin. 20 (2013) Paper 62, 17 pp.
[7] I. Gutman and N. Trinajstic, Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535 - 538.
[8] I. Gutman, B. Ruscic, N. Trinajstic and C. F. Wilcox, Graph theory and molecular orbitals. XII. Acyclic polyenes, J. Chem. Phys. 62 (1975) 3399 - 3405.
[9] F. Hausdorff, Grundzüge der Mengenlehre, Leipzig, German, 1914.
[10] P. V. Khadikar, S. Karmarkar and V. K. Agrawal, A novel PI index and its applications to QSPR/QSAR studies, J. Chem. Inf. Comput. Sci. 41 (2001) 934 - 949.
[11] M. K. Khalifeh, H. Yousefi-Azari and A. R. Ashrafi, Vertex and edge PI indices of Cartesian product graphs, Discrete Appl. Math. 156 (2008) 1780 - 1789.
[12] M. K. Khalifeh, H. Yousefi-Azari and A. R. Ashrafi, The first and second Zagreb indices of some graph operations, Discrete Appl. Math. 157 (2009) 804 - 811.
[13] M. Tavakoli, F. Rahbarnia and A. R. Ashrafi, Applications of generalized hierarchical product of graphs in computing the vertex and edge PI indices of chemical, Ric. Math. 63 (2014) 59 - 65.
[14] H. Wiener, Structural determination of the paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17 - 20.
[15] Y. N. Yeh and I. Gutman, On the sum of all distances in composite graphs, Discrete Math. 135 (1994) 359 - 365.