Interconnection Networks via Adjacencies and Their Vertex-Degree Based Graph Invariants
DOI:
https://doi.org/10.26713/cma.v14i1.1920Keywords:
Interconnection networks, Energy, Degree based topological indices, Integral graphsAbstract
Interconnection Networks are a boon to human made large computing systems which are often designed based on the need. In this paper, we address the question of obtaining an interconnection network to suit a specific need which is a cumbersome procedure. The methods for constructing infinitely large interconnection networks from any simple, undirected graph \(G\) is illustrated and their properties are discussed. Further, we study the behaviour of certain vertex-degree based graph invariants of the constructed networks under the transformations by means of graph operation and obtain explicit relations for energy and some degree-based topological indices. Also, we show that they can be computed in polynomial time for these constructed networks. By doing so, we also obtain new methods of constructing infinite families of integral graphs.
Downloads
References
C. Adiga, B. R. Rakshith and K. N. S. Krishna, Spectra of some new graph operations and some new classes of integral graphs, Iranian Journal of Mathematical Sciences and Informatics 13(1) (2018), 51 – 65, DOI: 10.7508/ijmsi.2018.1.005.
B. S. Anderson, C. Butts and K. Carley, The interaction of size and density with graph-level indices, Social Networks 21(3) (1999), 239 – 267, DOI: 10.1016/s0378-8733(99)00011-8.
A. T. Balaban, I. Motoc, D. Bonchev and O. Mekenyan, Topological indices for structure-activity correlations, in: Steric Effects in Drug Design, Topics in Current Chemistry, Vol. 114, Springer, Berlin — Heidelberg (1983), DOI: 10.1007/bfb0111212.
K. T. Balinska, D. M. Cvetkovic, Z. S. Radosavljevic, S. K. Simic and D. P. Stevanovic, A survey on integral graphs, Publikacije Elektrotehnickog Fakulteta – Serija: Matematika 13 (2002), 42 – 65, DOI: 10.2298/PETF0213042B.
A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Springer, New York, xiv + 250 pages (2011), DOI: 10.1007/978-1-4614-1939-6.
X. Chen and W. Xie, Energy of a hypercube and its complement, International Journal of Algebra 6(16) (2012), 799 – 805.
E. Cheng, K. Qiu and Z. Shen, Diagnosability of interconnection networks: past, present and future, International Journal of Parallel, Emergent and Distributed Systems 35(1) (2020), 2 – 8, DOI: 10.1080/17445760.2019.1655742.
M. Cohn, On the channel capacity of read/write isolated memory, Discrete Applied Mathematics 56(1) (1995), 1 – 8, DOI: 10.1016/0166-218x(93)e0130-q.
M. Dehmer, F. Emmert-Streib and Y. Shi, Interrelations of graph distance measures based on topological indices, PLOS ONE 9(4) (2014), e94985, DOI: 10.1371/journal.pone.0094985.
F. Emmert-Streib and M. Dehmer, Networks for systems biology: Conceptual connection of data and function, IET Systems Biology 5(3) (2011), 185 – 207, DOI: 10.1049/iet-syb.2010.0025.
F. Al Faisal, M. M. H. Rahman and Y. Inoguchi, 3D-TTN: a power efficient cost effective high performance hierarchical interconnection network for next generation green supercomputer, Cluster Computing 24 (2021), 2897 – 2908, DOI: 10.1007/s10586-021-03297-1.
Y.-Z. Fan, G.-D. Yu and Y. Wang, The chromatic number and the least eigenvalue of a graph, The Electronic Journal of Combinatorics 19(1) (2012), Article number: P39, DOI: 10.37236/2043.
T.-Y. Feng, A survey of interconnection networks, Computer 14(12) (1981), 12 – 27, DOI: 10.1109/c-m.1981.220290.
M. Ghasempour, J. Heathcote, J. Navaridas, L. A. Plana, J. Garside and M. Luján, Analysis of software and hardware-accelerated approaches to the simulation of unconventional interconnection networks, Simulation Modelling Practice and Theory 103 (2020), 102088, DOI: 10.1016/j.simpat.2020.102088.
I. Gutman, The energy of a graph: Old and new results, in: Algebraic Combinatorics and Applications, A. Betten, A. Kohnert, R. Laue and A. Wassermann (eds), Springer, Berlin — Heidelberg (2001), DOI: https://doi.org/10.1007/978-3-642-59448-9_13.
J. Hao, Theorems about Zagreb indices and modified Zagreb indices, MATCH Communications in Mathematical and in Computer Chemistry 65 (2011), 659 – 670, URL: https://match.pmf.kg.ac.rs/electronic_versions/Match65/n3/match65n3_659-670.pdf.
F. Harary and A. J. Schwenk, Which graphs have integral spectra?, in: Graphs and Combinatorics: Proceedings of the Capital Conference on Graph Theory and Combinatorics, George Washington University, June 18-22, 1973, Springer, Berlin — Heidelberg (1974).
R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, New York (1991), DOI: 10.1017/cbo9780511840371.
K. A. S. Immink, Codes for Mass Data Storage Systems, Shannon Foundation Publishers, The Netherlands (2004).
G. Indulal and A. Vijayakumar, Energies of some non-regular graphs, Journal of Mathematical Chemistry 42 (2007), 377 – 386, DOI: 10.1007/s10910-006-9108-7.
T. Jain, Nonblocking On-chip Interconnection Networks, Doctoral dissertation, Technischen Universität Kaiserslautern, Germany (2020), URL: https://kluedo.ub.rptu.de/frontdoor/deliver/index/docId/5976/file/Nonblocking_On-Chip_Interconnection_Networks.pdf.
M. Jurczyk, H. J. Siegel and C. Stunkel, Interconnection networks for parallel computers, Wiley Encyclopedia of Computer Science and Engineering, B. W. Wah (Ed.), Wiley, pp. 1613 – 1623 (2007), DOI: 10.1002/9780470050118.ecse197.
D. Lüdtke and D. Tutsch, The modeling power of CINSim: Performance evaluation of interconnection networks, Computer Networks 53(8) (2009), 1274 – 1288, DOI: 10.1016/j.comnet.2009.02.013.
J. Leskovec, J. Kleinberg and C. Faloutsos, Graphs over time: Densification laws, shrinking diameters and possible explanations, KDD’05: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining, Association for Computing Machinery, New York, USA (2005), pp. 177 – 187, DOI: 10.1145/1081870.1081893.
Q. Li and K. Q. Feng, On the largest eigenvalue of graphs, Acta Mathematicae Applicatae Sinica 2 (1979), 167 – 175.
J. Li, W. C. Shiu, W. H. Chan and A. Chang, On the spectral radius of graphs with connectivity at most k, Journal of Mathematical Chemistry 46 (2009), 340 – 346, DOI: 10.1007/s10910-008-9465-5.
X. Li, Y. Shi and I. Gutman, Graph Energy, Springer, New York (2012), DOI: 10.1007/978-1-4614-4220-2.
J. Liang and Q. Zhang, The t/s-diagnosability of hypercube networks under the PMC and comparison models, IEEE Access 5 (2017), 5340 – 5346, DOI: 10.1109/access.2017.2672602.
Y. Liao, J. Yin, D. Yin and L. Gao, DPillar: Dual-port server interconnection network for large scale data centers, Computer Networks 56(8) (2012), 2132 – 2147, DOI: 10.1016/j.comnet.2012.02.016.
L. S. de Lima, A. Mohammadian and C. S. Oliveira, On integral graphs with at most two vertices of degree larger than two, Linear Algebra and its Applications 584 (2020), 164 – 184, DOI: 10.1016/j.laa.2019.09.019.
H. Liu, M. Lu and F. Tian, Some upper bounds for the energy of graphs, Journal of Mathematical Chemistry 41 (2007), 45 – 57, DOI: 10.1007/s10910-006-9183-9.
J. Louis, A formula for the energy of circulant graphs with two generators, Journal of Applied Mathematics 2016 (2016), Article ID 1793978, DOI: 10.1155/2016/1793978.
L. Lovász and J. Pelikán, On the eigenvalues of trees, Periodica Mathematica Hungarica 3 (1973), 175 – 182, DOI: 10.1007/bf02018473.
M. Lv, J. Fan, J. Zhou, B. Cheng and X. Jia, The extra connectivity and extra diagnosability of regular interconnection networks, Theoretical Computer Science 809 (2020), 88 – 102, DOI: 10.1016/j.tcs.2019.12.001.
Z. Mihalic, D. Veljan, D. Amic, S. Nikolic, D. Plavšic and N. Trinajstic, The distance matrix in chemistry, Journal of Mathematical Chemistry 11 (1992), 223 – 258, DOI: 10.1007/bf01164206.
M. Morzy and T. Kajdanowicz, Graph energies of egocentric networks and their correlation with vertex centrality measures, Entropy 20(12) (2018), 916, DOI: 10.3390/e20120916.
S. M. Nabavinejad, M. Baharloo, K.-C. Chen, M. Palesi, T. Kogel and M. Ebrahimi, An overview of efficient interconnection networks for deep neural network accelerators, IEEE Journal on Emerging and Selected Topics in Circuits and Systems 10(3) (2020), 268 – 282, DOI: 10.1109/jetcas.2020.3022920.
H. Narumi and M. Katayama, Simple topological index: A newly devised index characterizing the topological nature of structural isomers of saturated hydrocarbons, Memoirs of the Faculty of Engineering, Hokkaido University 16(3) (1984), 209 – 214, URL: https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/38010/1/16(3)_209-214.pdf .
R. V. Solé and S. Valverde, Information theory of complex networks: on evolution and architectural constraints, in: Complex Networks, E. Ben-Naim, H. Frauenfelder and Z. Toroczkai (eds.), Lecture Notes in Physics, Vol. 650, Springer, Berlin — Heidelberg, DOI: 10.1007/978-3-540-44485-5_9.
B. Suntornpoch and Y. Meemark, Cayley graphs over a finite chain ring and GCD-graphs, Bulletin of the Australian Mathematical Society 93(3) (2016), 353 – 363, DOI: 10.1017/s0004972715001380.
S. S. Surya and P. Subbulakshmi, On the spectral parameters of certain cartesian products of graphs with P2, in: Mathematical Analysis and Computing – ICMAC 2019, R. N. Mohapatra, S. Yugesh, G. Kalpana and C. Kalaivani (eds.), Springer Proceedings in Mathematics & Statistics, Vol. 344, Springer, Singapore (2021), DOI: 10.1007/978-981-33-4646-8_31.
Y.-Y. Tan and Y.-Z. Fan, The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph, Linear Algebra and its Applications 433(4) (2010), 790 – 795, DOI: 10.1016/j.laa.2010.04.009.
K. J. Tinkler, The physical interpretation of eigenfunctions of dichotomous matrices, Transactions of the Institute of British Geographers 55 (1972), 17 – 46, DOI: 10.2307/621721.
R. E. Ulanowicz, Information theory in ecology, Computers and Chemistry 25(4) (2001), 393 – 399, DOI: 10.1016/s0097-8485(01)00073-0.
S. K. Vaidya and K. M. Popat, Energy of m-splitting and m-shadow graphs, Far East Journal of Mathematical Sciences 102(8) (2017), 1571 – 1578, DOI: 10.17654/ms102081571.
S. K. Vaidya and K. M. Popat, Some new results on energy of graphs, MATCH Communications in Mathematical and in Computer Chemistry 77 (2017), 589 – 594, URL: https://match.pmf.kg.ac.rs/electronic_versions/Match77/n3/match77n3_589-594.pdf.
T. Wang, L. Jia and F. Sun, Bounds of the spectral radius and the nordhaus-gaddum type of the graphs, The Scientific World Journal 2013 (2013), Article ID 472956, DOI: 10.1155/2013/472956.
P. M. Weichsel, The Kronecker product of graphs, Proceedings of the American Mathematical Society 13 (1962), 47 – 52, DOI: 10.1090/s0002-9939-1962-0133816-6.
T. Wilhelm and J. Hollunder, Information theoretic description of networks, Physica A: Statistical Mechanics and its Applications 385(1) (2007), 385 – 396, DOI: 10.1016/j.physa.2007.06.029.
J. Xu, Topological Structure and Analysis of Interconnection Networks, Network Theory and Applications series (NETA, Vol. 7), Springer, New York (2013), DOI: 10.1007/978-1-4757-3387-7.
R. Yasudo, K. Nakano, M. Koibuchi, H. Matsutani and H. Amano, Designing low-diameter interconnection networks with multi-ported host-switch graphs, Concurrency and Computation: Practice and Experience 35(11) (2020), e6115, DOI: 10.1002/cpe.6115.
F. Zahn, Energy-Efficient Interconnection Networks for High-Performance Computing, Doctoral dissertation, Ruprecht–Karls University, Heidelberg, German (2020), DOI: 10.11588/heidok.00029177.
B. Zhou and I. Gutman, Further properties of Zagreb indices, MATCH Communications in Mathematical and in Computer Chemistry 54 (2005), 233 – 239, URL https://match.pmf.kg.ac.rs/electronic_versions/Match54/n1/match54n1_233-239.pdf.
Q. Zhu, K. Thulasiraman, M. Xu and S. Radhakrishnan, Hybrid PMC (HPMC) fault model and diagnosability of interconnection networks, AKCE International Journal of Graphs and Combinatorics 17(3) (2020), 755 – 760, DOI: 10.1016/j.akcej.2019.12.008.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
