{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T06:54:34Z","timestamp":1657695274269},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,6]]},"abstract":"<jats:p> Interconnection networks of various topologies have been widely used in designing multiprocessor architectures. Study of graph theoretical or combinatorial properties of such networks help us better understand them, as well as develop on these architectures more efficient parallel algorithms including fault-tolerant communication\/routing algorithms. In this paper, we analyze a broad class of interconnection networks from a new angle by looking into the corresponding graph spectra (i.e., eigenvalues and their multiplicities). Since eigenvalues of the edjacency matrix of a graph can reveal many important properties of the graph that are closely related to its combinatorial invariants, we believe that the study of spectra of interconnection networks can be a more unified approach to studying their topological properties. As a first step) in this direction, here we mainly concentrate on finding out the spectra of some of the most studied interconnection networks. Specifically, after a brief survey of results that relate spectra of graphs to their structural properties, we summarize the existing results for eigenvalues and multiplicities of several popular interconnection networks such as the hypercube and mesh. We also derive some of these results in a more straightforward way. Then we present new results on spectra for some other known networks such as the line graph of the hypercube, followed by experimental results on a few others including the star and pancake networks. <\/jats:p>","DOI":"10.1142\/s0129054103001790","type":"journal-article","created":{"date-parts":[[2003,7,24]],"date-time":"2003-07-24T11:23:50Z","timestamp":1059045830000},"page":"371-389","source":"Crossref","is-referenced-by-count":4,"title":["Interconnection Networks and Their Eigenvalues"],"prefix":"10.1142","volume":"14","author":[{"given":"Ke","family":"Qiu","sequence":"first","affiliation":[{"name":"Computer Science, Acadia University, Wolfville, Nova Scotia, B4P 2R6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sajal K.","family":"Das","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, University of Texas, Arlington, Texas 76019, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1109\/12.21148","volume":"38","author":"Akers S. B.","journal-title":"IEEE Transaction on Computers"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1989-0965008-X"},{"key":"rf4","series-title":"CBMS","volume-title":"Spectral Graph Theory","volume":"92","author":"Chung F. R. K.","year":"1997"},{"key":"rf5","volume-title":"Spectra of Graphs","author":"Cvetkovi\u0107 D. M.","year":"1995"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1995-00571-9"},{"key":"rf7","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"Leighton F. T.","year":"1992"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/358645.358660"},{"key":"rf9","first-page":"16","volume":"22","author":"Qiu K.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1109\/12.21149"},{"key":"rf12","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"2001"},{"key":"rf13","first-page":"330","volume":"42","author":"Wilf H. S.","journal-title":"Journal of London Math. Society"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103001790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:38:18Z","timestamp":1565138298000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103001790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,6]]},"references-count":11,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,6]]}},"alternative-id":["10.1142\/S0129054103001790"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103001790","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,6]]}}}