Construction and analysis of graph models for multiprocessor interconnection networks
DOI:
https://doi.org/10.2298/YJOR200915017HKeywords:
Interconnection Networks, Graph Tightness, Line Graph, Chromatic Number, Chromatic IndexAbstract
A graph G can serve as a model for the Multiprocessor Interconnection Networks (MINs) in which the vertices represent the processors, while the edges represent connections between processors. This paper presents several graphs that could qualify as models for efficient MINs based on the small values of the graph tightness previously introduced by Cvetković and Davidović in 2008. These graphs are constructed using some well-known and widely used graph operations. The tightness values of these graphs range from O(4√N) to O(√N), where N is the order of the graph under consideration. Also, two new graph tightness values, namely Third type mixed tightness t3(G) and Second type of Structural tightness t4(G) are defined in this paper. It has been shown that these tightness types are easier to calculate than the others for the considered graphs. Moreover, their values are significantly smaller.References
Behzad, M., “A characterization of total graphs,” Proceedings of the American Mathematical Society, 26 (3) (1970) 383–389.
Brooks, R. L., “On colouring the nodes of a network,” Mathematical Proceedings of the Cambridge Philosophical Society, 37 (2) (1941) 194–197.
Brouwer, A. E., Cohen, A. M., and Neumaier, A., Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
Brouwer, A. E., and Haemers, H. W., Spectra of graphs, Springer, 2011.
Chartrand, G., and Zhang, P., Chromatic graph theory, Discrete Mathematics and its Applications, CRC Press, Boca Raton, FL, 2009.
Cvetković, D., Graphs and their spectra, Publikacije Elekrotehničkog fakulteta, Serija Matematika i fizika, (354/356) (1971) 1-50.
Cvetković, D., and Davidović, T., “Application of some graph invariants to the analysis of multiprocessor interconnection networks,” Yugoslav Journal of Operations Research, 18 (2) (2008) 173–186.
Cvetković, D., Davidović, T., and Jovanović, I., “Some new models for multiprocessor interconnection networks,” Yugoslav Journal of Operations Research, 26 (4) (2016) 423–439.
Cvetković, D., Doob, M. M., and Sachs, H., Spectra of graphs: Theory and applications, Johann Ambrosius Barth, Heidelberg-Leipzig, 3rd edition, 1995.
Elsässer, R., Kralovic, R., and Monien, B., “Sparse topologies with small spectrum size,” Theoretical Computer Science, 307 (2003) 549–565.
Hammack, R., Imrich, W., and Klavžar, S., Handbook of product graphs, CRC Press, 2011.
Harary, F., and Norman, Z. R., “Some properties of line digraphs,” Rendiconti del Circolo Matematico di Palermo, 9 (2) (1960) 161–168.
Jaradat, M. M. M., “On the Anderson-Lipman conjecture and some related problems,” Discrete Mathematics, 297 (1-3) (2005) 167–173.
Krausz, J., “Démonstration nouvelle d’une thèoreme de Whitney sur les réseaux,” Mat. Fiz. Lapok, 50 (1) (1943) 75–85.
Mahamoodian, E. S., “On edge-colorability of Cartesian products of graphs,” Canadian Mathematical Bulletin, 24 (1) (1981) 107–108.
Stein, W., Sage mathematics software. http://www.sagemath.org/, 2007.
Vizing, G. V., “Critical graphs with given chromatic class,” (in Russian). Metody Discret. Analiz., 5 (1965) 9–17.
Whitney, H., “Congruent graphs and the connectivity of graphs,” American Journal of Mathematics, 54 (1) (1932) 150–168.
Wilf, H. S., “The eigenvalues of a graph and its chromatic number,” Journal of the London Mathematical Society, s1-42 (1) (1967) 330–332.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
