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 -

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

Volume 4, Issue 2
Special Issue: Spectral Graph Theory and Mathematical Chemistry with Connection to Computer Science
Autumn 2019
Pages 281-291