| Preface |
|
ix | |
|
Interconnection Networks and Graphs |
|
|
1 | (38) |
|
Graphs and Interconnection Networks |
|
|
1 | (7) |
|
|
|
2 | (1) |
|
|
|
3 | (3) |
|
|
|
6 | (2) |
|
Basic Concepts and Notations on Graphs |
|
|
8 | (8) |
|
Subgraphs and Operations of Graphs |
|
|
9 | (1) |
|
|
|
10 | (2) |
|
Paths, Cycles and Connected Graphs |
|
|
12 | (2) |
|
Adjacency Matrices and Other Concepts |
|
|
14 | (2) |
|
Trees, Embeddings and Planar Graphs |
|
|
16 | (6) |
|
|
|
16 | (2) |
|
|
|
18 | (3) |
|
Planar Graphs and Layout of VLSI Circuits |
|
|
21 | (1) |
|
Transmission Delay and Diameter |
|
|
22 | (8) |
|
|
|
23 | (3) |
|
Average Distance of Graphs |
|
|
26 | (2) |
|
|
|
28 | (2) |
|
Fault Tolerance and Connectivity |
|
|
30 | (5) |
|
|
|
30 | (1) |
|
|
|
31 | (2) |
|
Fault Tolerance of Networks |
|
|
33 | (2) |
|
Basic Principles of Network Design |
|
|
35 | (4) |
|
|
|
35 | (2) |
|
Basic Principles of Network Design |
|
|
37 | (2) |
|
Design Methodology of Topological Structure of Interconnection Networks |
|
|
39 | (66) |
|
|
|
40 | (12) |
|
Line Graph of Undirected Graph |
|
|
40 | (2) |
|
|
|
42 | (2) |
|
Connectivity and Diameter of Line Graphs |
|
|
44 | (1) |
|
Eulerian and Hamiltonian Properties |
|
|
45 | (1) |
|
|
|
46 | (2) |
|
Edge-Connectivity of Line Graphs |
|
|
48 | (4) |
|
|
|
52 | (24) |
|
|
|
52 | (5) |
|
|
|
57 | (2) |
|
|
|
59 | (3) |
|
Connectivity of Transitive Graphs |
|
|
62 | (3) |
|
|
|
65 | (2) |
|
Transitivity of Cayle Graphs |
|
|
67 | (3) |
|
Atoms and Connectivity of Cayley Graphs |
|
|
70 | (4) |
|
Vertex-Transitive Graphs with Prime Order |
|
|
74 | (2) |
|
|
|
76 | (15) |
|
Cartesian Product of Undirected Graphs |
|
|
76 | (2) |
|
Cartesian Product of Digraphs |
|
|
78 | (1) |
|
Some Remarks on Cartesian Products |
|
|
79 | (2) |
|
Diameter and Connectivity of Cartesian Products |
|
|
81 | (3) |
|
Other Properties of Cartesian Products |
|
|
84 | (2) |
|
Cartesian Product of Cayley Graphs |
|
|
86 | (5) |
|
A Basic Problem in Optimal Design |
|
|
91 | (14) |
|
Undirected (d, k)-Graph Problems |
|
|
91 | (5) |
|
Directed (d, k)-Graph Problems |
|
|
96 | (3) |
|
Bipartite (d, k)-Graph Problems |
|
|
99 | (2) |
|
Planar (d, k)-Graph Problems |
|
|
101 | (1) |
|
Relations between Diameter and Connectivity |
|
|
102 | (3) |
|
Well-known Topological Structures of Interconnection Networks |
|
|
105 | (82) |
|
|
|
105 | (16) |
|
Two Equivalent Definitions |
|
|
106 | (1) |
|
|
|
107 | (3) |
|
|
|
110 | (2) |
|
|
|
112 | (1) |
|
|
|
113 | (3) |
|
|
|
116 | (2) |
|
Some Enhancements on Hypercubes |
|
|
118 | (3) |
|
|
|
121 | (18) |
|
Three Equivalent Definitions |
|
|
121 | (3) |
|
Eulerian and Hamiltonian Properties |
|
|
124 | (2) |
|
Uniqueness of Shortest Paths |
|
|
126 | (5) |
|
De Bruijn Undirected Graphs |
|
|
131 | (1) |
|
Generalized de Bruijn Digraphs |
|
|
131 | (7) |
|
Comparison with Hypercubes |
|
|
138 | (1) |
|
|
|
139 | (9) |
|
Three Equivalent Definitions |
|
|
139 | (2) |
|
|
|
141 | (1) |
|
|
|
142 | (1) |
|
Generalized Kautz Digraphs |
|
|
142 | (3) |
|
Connectivity of Generalized Kautz Digraphs |
|
|
145 | (3) |
|
|
|
148 | (23) |
|
|
|
148 | (2) |
|
|
|
150 | (4) |
|
Diameter of Double Loop Networks |
|
|
154 | (6) |
|
Optimal Design of Double Loop Networks |
|
|
160 | (5) |
|
Circulant Networks and Basic Properties |
|
|
165 | (6) |
|
Other Topological Structures of Networks |
|
|
171 | (16) |
|
Mesh Networks and Grid Networks |
|
|
171 | (2) |
|
|
|
173 | (2) |
|
|
|
175 | (3) |
|
|
|
178 | (4) |
|
|
|
182 | (3) |
|
|
|
185 | (1) |
|
Shuffle-Exchange Networks |
|
|
186 | (1) |
|
Fault-Tolerant Analysis of Interconnection Networks |
|
|
187 | (120) |
|
Routings in Interconnection Networks |
|
|
187 | (20) |
|
Forwarding Index of Routing |
|
|
188 | (8) |
|
Edge-Forwarding Index of Routing |
|
|
196 | (2) |
|
Delay of Fault-Tolerant Routing |
|
|
198 | (4) |
|
|
|
202 | (5) |
|
|
|
207 | (28) |
|
|
|
207 | (8) |
|
|
|
215 | (12) |
|
|
|
227 | (5) |
|
Fault-Tolerant Diameters of Some Networks |
|
|
232 | (3) |
|
Menger-Type Problems in Parallel Systems |
|
|
235 | (20) |
|
Disjoint Paths for Bounded Length |
|
|
235 | (7) |
|
Menger Number and Bounded Connectivity |
|
|
242 | (4) |
|
Edge Disjoint Paths for Bounded Length |
|
|
246 | (3) |
|
Disjoint Paths for Exceeded Length |
|
|
249 | (2) |
|
Rabin Numbers of Networks |
|
|
251 | (4) |
|
Wide Diameter of Networks |
|
|
255 | (20) |
|
Containers and Basic Properties |
|
|
255 | (1) |
|
Wide Diameter and Basic Results |
|
|
256 | (3) |
|
Wide-Diameter on Regular Graphs |
|
|
259 | (2) |
|
Wide-Diameter on Cartesian Products |
|
|
261 | (4) |
|
Wide-Diameter and Independence Number |
|
|
265 | (3) |
|
Wide-Diameter and Fault-Tolerant Diameter |
|
|
268 | (2) |
|
Wide-Diameters of Some Well-Known Networks |
|
|
270 | (4) |
|
Wide Diameter for Edge Variation |
|
|
274 | (1) |
|
(l, w)-Independence and -Dominating Numbers |
|
|
275 | (13) |
|
(l, w)-Independence Numbers |
|
|
275 | (4) |
|
(l, w)-Dominating Numbers |
|
|
279 | (3) |
|
(l, 1)-Independence and -Dominating Numbers |
|
|
282 | (5) |
|
Some (l, w)-Dominating Numbers |
|
|
287 | (1) |
|
Restricted Fault-Tolerance of Networks |
|
|
288 | (19) |
|
Restricted Connectivity and Diameter |
|
|
288 | (4) |
|
Restricted Edge-Connectivity |
|
|
292 | (3) |
|
|
|
295 | (4) |
|
Restricted Edge-Connectivity of Transitive Graphs |
|
|
299 | (3) |
|
Generalized Restricted Edge-Connectivity |
|
|
302 | (5) |
| Bibliography |
|
307 | (22) |
| List of Symbols |
|
329 | (8) |
| Subject Index |
|
337 | |
