The subset-strong product of graphs
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.
Keywords
strong products; adjacency matrix; prism networks; Zagreb indices; hierarchical product
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.
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.
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.
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.
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.
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.
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.
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.
M. Eliasi, Gh. Raeisi, and B. Taeri, Wiener index of some graph operations, Discrete Appl. Math. 160 (2012), no. 9, 1333–1344.
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.
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.
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.
R.S. Hales, Numerical invariants and the strong product of graphs, J. Combinatorial Theory Ser. B 15 (1973), 146–155.
R. Hammack, W. Imrich, and S. Klavžar, Handbook of Product Graphs, CRC Press, Boca Raton, FL, 2011.
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.
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.
A. Kaveh and K. Koohestani, Graph products for configuration processing of space structures, Comput. Struct. 86 (2008), no. 11–12, 1219–1231.
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.
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.
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.
S. Klavžar, Strong products of χ-critical graphs, Aequationes Math. 45 (1993), no. 2–3, 153–162.
S. Klavžar and U. Milutinović, Strong products of Kneser graphs, Discrete Math. 133 (1994), no. 1–3, 297–300.
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.
Z. Luo, Applications on hyper-Zagreb index of generalized hierarchical product graphs, J. Comput. Theor. Nanosci. 13 (2016), no. 10, 7355–7361.
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.
K. Pattabiraman, S. Nagarajan, and M. Chendrasekharan, Zagreb indices and coindices of product graphs, J. Prime Res. Math. 10 (2014), 80–91.
G. Sabidussi, Graph multiplication, Math. Z. 72 (1959), 446–457.
S. Špacapan, Connectivity of strong products of graphs, Graphs Combin. 26 (2010), no. 3, 457–467.
B. Zhou, Zagreb indices, MATCH Commun. Math. Comput. Chem. 52 (2004), 113–118.
B. Zhou and I. Gutman, Relations between Wiener, hyper-Wiener and Zagreb indices, Chem. Phys. Lett. 394 (2004), no. 1–3, 93–95.
B. Zhou and I. Gutman, Further properties of Zagreb indices, MATCH Commun. Math. Comput. Chem. 54 (2005), no. 1, 233–239.
Department of Mathematics, Khansar Campus, University of Isfahan Iran, Islamic Republic of
https://orcid.org/0000-0003-0721-7221
The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.
- License
This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license. - Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. - User Rights
Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor. - Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
