Some Applications of Strong Product

Document Type : Original Scientific Paper


Department of Applied Mathematics Ferdowsi University of Mashhad P. O. Box 1159, Mashhad 91775, I. R. Iran


Let G and H be graphs. The strong product GH of graphs G and H is the graph with vertex set V(G)V(H) and u=(u1, v1) is adjacent with v= (u2, v2) whenever (v1 = v2 and u1 is adjacent with u2) or (u1 = u2 and v1 is adjacent with v2) or (u1 is adjacent with u2 and v1 is adjacent with v2). In this paper, we first collect the earlier results about strong product and then we present applications of these results in working with some important graphs
such as Fence graphs.


Main Subjects

1. A. R. Ashrafi, T. Došlić, A. Hamzeh, Extremal graphs with respect to the Zagreb coindices, MATCH Commun. Math. Comput. Chem. 65 (1) (2011) 85–92.
2. A. R. Ashrafi, T. Došlić, M. Saheli, The eccentric connectivity index of TUC4C8(R) nanotubes, MATCH Commun. Math. Comput. Chem. 65 (1) (2011) 221–230.
3. A. R. Ashrafi, M. Saheli, M. Ghorbani, The eccentric connectivity index of nanotubes and nanotori, J. Comput. Appl. Math. 235 (2011) 4561–4566.
4. G. G. Cash, Polynomial expressions for the hyper-Wiener index of extended hydrocarbon networks, Comput. Chem. 25 (2001) 577–582.
5. G. G. Cash, Relationship between the Hosoya polynomial and the hyperWiener index, Appl. Math. Lett. 15 (2002) 893–895.
6. A. A. Dobrymin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (2001) 211–249.
7. A. A. Dobrymin, I. Gutman, S. Klavšar, P. Žigert, Wiener index of hexagonal systems, Acta Appl. Math. 72 (2002) 247–294.
8. S. Gupta, M. Singh, A. K. Madan, Eccentric distance sum: a novel graph invariant for predicting biological and physical properties, J. Math. Anal. Appl. 275 (2002) 386–401.
9. I. Gutman, Relation between hyper-Wiener and Wiener index, Chem. Phys. Lett. 364 (2002) 352–356.
10. I. Gutman, N. Trinajstić, Graph theory and molecular orbitals. Total ф- electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972) 535–538.
11. R. Hammack, W. Imrich, S. Klavšar, Handbook of Product Graphs, Second edition, CRC Press, Boca Raton, FL, (2011).
12. H. Hosoya, Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bull. Chem. Soc. Jpn. 44 (1971) 2332–2339.
13. A. Ilić, I. Gutman, Eccentric connectivity index of chemical trees, MATCH Commun. Math. Comput. Chem. 65 (2011) 731–744.
14. M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi, The hyper-Wiener index of graph operations, Comput. Math. Appl. 56 (2008) 1402–1407.
15. S. Klavšar, P. Žigert, I. Gutman, An algorithm for the calculation of the hyper-Wiener index of benzenoid hydrocarbons, Comput. Chem. 24 (2000) 229–233.
16. D. J. Klein, I. Lukovits, I. Gutman, On the definition of the hyper-Wiener index for cycle-containing structures, J. Chem. Inf. Comput. Sci. 35 (1995) 50–52.
17. M. J. Morgan, S. Mukwembi, H. C. Swart, On the eccentric connectivity index of a graph, Discrete Math. 311 (2011) 1229–1234.
18. B. E. Sagan, Y. -N. Yeh, P. Zhang, The Wiener polynomial of a graph, Int. J. Quant. Chem. 60 (5) (1996) 959–969.
19. V. Sharma, R. Goswami, A. K. Madan, Eccentric connectivity index: a novel highly discriminating topological descriptor for structure property and structure activity studies, J. Chem. Inf. Comput. Sci. 37 (1997) 273–282.
20. M. Tavakoli, F. Rahbarnia, A. R. Ashrafi, Note on strong product of graphs, Kragujevac J. Math. 37 (1) (2013) 187–193.
21. H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17–20.
22. G. Yu, L. Feng, A. Ilić, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99–107.
23. B. Zhou, Zagreb indices, MATCH Commun. Math. Comput. Chem. 52 (2004) 113–118.
24. B. Zhou, Z. Du, On eccentric connectivity index, MATCH Commun. Math. Comput. Chem. 63 (2010) 181–198.
25. B. Zhou, I. Gutman, Relations between Wiener, hyper-Wiener and Zagreb indices, Chem. Phys. Lett. 394 (2004) 93–95.