GRAPH THEORY AND INTERCONNECTION NETWORKS

The advancement of large scale integrated circuit technology has enabled the construction of complex interconnection networks. Graph theory provides a fundamental tool for designing and analyzing such networks. Graph Theory and Interconnection Networks provides a thorough understanding of these interrelated topics. After a brief introduction to graph terminology, the book presents well-known interconnection networks as examples of graphs, followed by in-depth coverage of Hamiltonian graphs. Different types of problems illustrate the wide range of available methods for solving such problems. The text also explores recent progress on the diagnosability of graphs under various models.

1 Fundamental Concepts
2 Applications on Graph Isomorphisms
3 Distance and Diameter
4 Trees
5 Eulerian Graphs and Digraphs
6 Matchings and Factors
7 Connectivity
8 Graph Coloring
9 Hamiltonian Cycles
10 Planar Graphs
11 Optimal k-Fault-Tolerant Hamiltonian Graphs
12 Optimal 1-Fault-Tolerant Hamiltonian Graphs
13 Optimal k-Fault-Tolerant Hamiltonian-Laceable Graphs
14 Spanning Connectivity
15 Cubic 3*-Connected Graphs and Cubic 3*-Laceable Graphs
16 Spanning Diameter
17 Pancyclic and Panconnected Property
18 Mutually Independent Hamiltonian Cycles
19 Mutually Independent Hamiltonian Paths
20 Topological Properties of Butterfly Graphs
21 Diagnosis of Multiprocessor Systems