Hsu L. Graph Theory and Interconnection Networks 2008

Textbook in PDF format

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.
Fundamental Concepts
Applications on Graph Isomorphisms
Distance and Diameter
Trees
Eulerian Graphs and Digraphs
Matchings and Factors
Connectivity
Graph Coloring
Hamiltonian Cycles
Planar Graphs
Optimal k-Fault-Tolerant Hamiltonian Graphs
Optimal 1-Fault-Tolerant Hamiltonian Graphs
Optimal k-Fault-Tolerant Hamiltonian-Laceable Graphs
Spanning Connectivity
Cubic 3∗-Connected Graphs and Cubic 3∗-Laceable Graphs
Spanning Diameter
Pancyclic and Panconnected Property
Mutually Independent Hamiltonian Cycles
Mutually Independent Hamiltonian Paths
Topological Properties of Butterfly Graphs
Diagnosis of Multiprocessor Systems