The Subset-Strong Product of Graphs

Eliasi, Mehdi

doi:10.2478/amsil-2023-0029

Abstract

In this paper, we introduce the subset-strong product of graphs and give a method for calculating the adjacency spectrum of this product. In addition, exact expressions for the first and second Zagreb indices of the subset-strong products of two graphs are reported. Examples are provided to illustrate the applications of this product in some growing graphs and complex networks.

References

W.N. Anderson and T.D. Morley, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra 18 (1985), no. 2, 141–145.
Search in Google Scholar Back to article
D. Archambault, T. Munzner, and D. Auber, TopoLayout: Multilevel graph layout by topological features, IEEE Trans. Vis. Comput. Graph. 13 (2007), no. 2, 305–317.
Search in Google Scholar Back to article
D. Archambault, T. Munzner, and D. Auber, GrouseFlocks: Steerable exploration of graph hierarchy space, IEEE Trans. Vis. Comput. Graph. 14 (2008), no. 4, 900–913.
Search in Google Scholar Back to article
M. Arezoomand and B. Taeri, Zagreb indices of the generalized hierarchical product of graphs, MATCH Commun. Math. Comput. Chem. 69 (2013), no. 1, 131–140.
Search in Google Scholar Back to article
L. Barrière, C. Dalfó, M.A. Fiol, and M. Mitjana, The generalized hierarchical product of graphs, Discrete Math. 309 (2009), no. 12, 3871–3881.
Search in Google Scholar Back to article
J. Braun, A. Kerber, M. Meringer, and C. Rücker, Similarity of molecular descriptors: the equivalence of Zagreb indices and walk counts, MATCH Commun. Math. Comput. Chem. 54 (2005), no. 1, 163–176.
Search in Google Scholar Back to article
Q. Ding, W. Sun, and F. Chen, Applications of Laplacian spectra on a 3-prism graph, Modern Phys. Lett. B. 28 (2014), no. 2, 1450009, 12 pp.
Search in Google Scholar Back to article
M. Eliasi and A. Iranmanesh, The hyper-Wiener index of the generalized hierarchical product of graphs, Discrete Appl. Math. 159 (2011), no. 8, 866–871.
Search in Google Scholar Back to article
M. Eliasi, Gh. Raeisi, and B. Taeri, Wiener index of some graph operations, Discrete Appl. Math. 160 (2012), no. 9, 1333–1344.
Search in Google Scholar Back to article
J. Feigenbaum and A.A. Schäffer, Finding the prime factors of strong direct product graphs in polynomial time, Discrete Math. 109 (1992), no. 1–3, 77–102.
Search in Google Scholar Back to article
D.C. Fisher, J. Ryan, G. Domke, and A. Majumdar, Fractional domination of strong direct products, Discrete Appl. Math. 50 (1994), no. 1, 89–91.
Search in Google Scholar Back to article
I. Gutman and N. Trinajstić, Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons, Chem. Phys. Lett. 17 (1972), no. 4, 535–538.
Search in Google Scholar Back to article
R.S. Hales, Numerical invariants and the strong product of graphs, J. Combinatorial Theory Ser. B 15 (1973), 146–155.
Search in Google Scholar Back to article
R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, CRC Press, Boca Raton, FL, 2011.
Search in Google Scholar Back to article
Y.P. Hong, R.A. Horn, and C.R. Johnson, On the reduction of pairs of Hermitian or symmetric matrices to diagonal form by congruence, Linear Algebra Appl. 73 (1986), 213–226.
Search in Google Scholar Back to article
A. Kaveh and H. Fazli, Approximate eigensolution of Laplacian matrices for locally modified graph products, J. Comput. Appl. Math. 236 (2011), no. 6, 1591–1603.
Search in Google Scholar Back to article
A. Kaveh and K. Koohestani, Graph products for configuration processing of space structures, Comput. Struct. 86 (2008), no. 11–12, 1219–1231.
Search in Google Scholar Back to article
A. Kaveh and R. Mirzaie, Minimal cycle basis of graph products for the force method of frame analysis, Comm. Numer. Methods Engrg. 24 (2008), no. 8, 653–669.
Search in Google Scholar Back to article
M.H. Khalifeh, H. Yousefi-Azari, and A.R. Ashrafi, The hyper-Wiener index of graph operations, Comput. Math. Appl. 56 (2008), no. 5, 1402–1407.
Search in Google Scholar Back to article
M.H. Khalifeh, H. Yousefi-Azari, and A.R. Ashrafi, The first and second Zagreb indices of some graph operations, Discrete Appl. Math. 157 (2009), no. 4, 804–811.
Search in Google Scholar Back to article
S. Klavžar, Strong products of χ-critical graphs, Aequationes Math. 45 (1993), no. 2–3, 153–162.
Search in Google Scholar Back to article
S. Klavžar and U. Milutinović, Strong products of Kneser graphs, Discrete Math. 133 (1994), no. 1–3, 297–300.
Search in Google Scholar Back to article
J.-B. Liu, J. Cao, A. Alofi, A. AL-Mazrooei, and A. Elaiw, Applications of Laplacian spectra for n-prism networks, Neurocomputing 198 (2016), 69–73.
Search in Google Scholar Back to article
Z. Luo, Applications on hyper-Zagreb index of generalized hierarchical product graphs, J. Comput. Theor. Nanosci. 13 (2016), no. 10, 7355–7361.
Search in Google Scholar Back to article
S. Nikolić, G. Kovačević, A Miličević, and N. Trinajstić, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003), no. 2, 113–124.
Search in Google Scholar Back to article
K. Pattabiraman, S. Nagarajan, and M. Chendrasekharan, Zagreb indices and coindices of product graphs, J. Prime Res. Math. 10 (2014), 80–91.
Search in Google Scholar Back to article
G. Sabidussi, Graph multiplication, Math. Z. 72 (1959), 446–457.
Search in Google Scholar Back to article
S. Špacapan, Connectivity of strong products of graphs, Graphs Combin. 26 (2010), no. 3, 457–467.
Search in Google Scholar Back to article
B. Zhou, Zagreb indices, MATCH Commun. Math. Comput. Chem. 52 (2004), 113–118.
Search in Google Scholar Back to article
B. Zhou and I. Gutman, Relations between Wiener, hyper-Wiener and Zagreb indices, Chem. Phys. Lett. 394 (2004), no. 1–3, 93–95.
Search in Google Scholar Back to article
B. Zhou and I. Gutman, Further properties of Zagreb indices, MATCH Commun. Math. Comput. Chem. 54 (2005), no. 1, 233–239.
Search in Google Scholar Back to article

The Subset-Strong Product of Graphs

Abstract

Paradigm

My account