Large interconnection networks with given degree and diameter

Research Doctorate - Doctor of Philosophy (PhD)This thesis investigates and provides several answers for one of the most representative open problems in the design of interconnection networks. In the last few decades, the ability to design interconnection networks satisfying practical requirements and constraints has become a topic of major interest. In most circumstances, however, this has turned out to be a rather challenging task, leading to questions that have become the source of more than one interesting unsolved problem. One of these problems that has received significant attention deals with the design of networks as large as possible in terms of the number of nodes, given a limit on the number of connections attached to a node and a limit on the distance between any two nodes of the network. When translated to graph-theoretical terms this leads to the Degree/Diameter Problem, which asks for the largest number of vertices in a graph (and the graph itself) with a given maximum degree and diameter. The Degree/Diameter problem has been investigated since it was stated in 1964, yet is has endured as an open problem for more than fifty years now. A generous number of partial outcomes have been obtained to date, without narrowing the considerable gap remaining between the currently known upper and lower bounds for most degrees and diameters. The networks in question may be subject to further classification, such as being planar or bipartite, which restricts the Degree/Diameter Problem to the class of graphs under consideration. In this thesis we make substantial contributions to the Degree/Diameter Problem by providing improvements in the two traditional research directions: lowering the upper bounds for by proving the non-existence of graphs, and increasing the lower bounds by finding or giving constructions of ever larger graphs with given degree and diameter. The methodology used relies on a mixture of combinatorial approaches, graph compounding techniques, as well as algorithmic techniques and computer search. Our outcomes cover four of the most prominent classes of graphs studied: general graphs, bipartite graphs, circulant graphs, and graphs embeddable on surfaces. Among others, we obtain the following results: For the class of bipartite graphs, we use combinatorial approaches to improve the current upper bounds for more than two thirds of all possible combinations of degree and diameter. In a partially computer assisted proof, we prove that the largest known bipartite graph of degree 7 and diameter 3 is optimal. We also find by computer search a bipartite graph of degree 11 and diameter 3, thus improving the former lower bound by 4 vertices. ; For the class of general graphs, we use a similar strategy to improve the current upper bounds for more than one half of all possible combinations of degree and diameter. ; For the class of circulant graphs, we design and implement an efficient algorithm to find circulant graphs of small diameter. We find 15 largest known circulant graphs, with diameters ranging from 3 to 5 and degrees between 8 and 15. Using a combination of this algorithm and the cartesian product of graphs, we develop a search procedure to find 41 circulant graphs, with diameters ranging from 4 to 10 and degrees between 10 and 16, for which no previous graph had been found in the past. ; For the class of graphs embeddable in an arbitrary fixed surface, we use graph compounding to obtain graphs with orders improving the former lower bounds by a factor of 4. In addition, we construct a number of largest known planar and toroidal graphs. Finally, we present some final considerations about our work, and state a few conjectures providing support for future research in the design of interconnection networks and the Degree/Diameter Problem