Preface 

The advent of very large scale integrated circuit technology has enabled the construction of very complex and large interconnection networks. By most accounts, the next generation of supercomputers will achieve its gains by increasing the number of processing elements, rather than by using faster processors. The most difficult technical problem in constructing a supercomputer will be the design of the interconnection network through which the processors communicate. Selecting an appropriate and adequate topological structure of interconnection networks will become a critical issue, on which many research efforts have been made over the past decade. The book is aimed to attract the readers' attention to such an important research area.

Graph theory is a fundamental and powerful mathematical tool for designing and analyzing interconnection networks, since the topological structure of an interconnection network is a graph. This fact has been universally accepted by computer scientists and engineers. This book provides the most basic problems, concepts and well-established results on the topological structure and analysis of interconnection networks in the language of graph theory. The material originates from a vast amount of literature, but the theory presented is developed carefully and skillfully. The treatment is generally self-contained, and most stated results are proved. No exercises are explicitly exhibited, but there are some stated results whose proofs are left to the reader to consolidate his understanding of the material. 

The book consists of four chapters. The first chapter introduces how to model an interconnection network by a graph and provides a self-contained exposition of the basic graph-theoretic concepts, terminology, notation and the corresponding backgrounds of networks as well as the basic principles of network design. Some basic results on graph theory used in the book are stated. The second chapter presents three major methods for large-scale network design: line graph method, Cayley method and cartesian product method. The fundamental properties of the graphs constructed by these methods are presented in details. The (d, k)-graph problem is briefly discussed. As applications of the methods, the third chapter provides four classes of the most well-known network structures: hypercube, de Bruijn, Kautz and double loop networks and their many desirable properties as well. At the end of this chapter, other common network structures such as mesh, grid, pyramid, cube-connected cycle, butterfly, omega, and shuffle-exchange networks are simply mentioned. The fourth chapter is a focal point of the book, from which the reader can easily find some interesting research issues to study further. It presents some basic issues and research results in analysis of fault-tolerant network consisting of six research aspects, involving routing, Menger-type problems in parallel systems, fault-tolerant diameter, wide diameter, (l, w)-dominating number and restricted fault tolerance.

Reading the book is not difficult for readers familiar with elementary graph theory. The book will be useful to those readers who intend to start research in design and analysis of interconnection network structures, and students in computer science and applied mathematics, theoretic computer scientists, engineers, designer of interconnection networks, applied mathematicians and other readers who are interested in interconnection networks.

The book is developed from the text for an advanced undergraduate and first-year postgraduate course in graph theory and computer science in one semester given at University of Science and Technology of China (USTC). I would like to thank Graduate School and Department of Mathematics of USTC for their support and encouragement.

I avail myself of this opportunity to express my heartfelt gratitude to Professor Qiao Li for his continuous help, to Professor Ding-Zhu Du for his encouragement and recommendation of the book as a member of the book series `` Network Theory and Applications", to Professor F. K. Hwang for his valuable suggestions, to Processor D. Frank Hsu for his bringing my research interest to the subject when he was inviting USTC in 1992, and to Professor Yuke Wang for his help whenever possible.

Finally, I would like to thank my son and postgraduate student, Keli Xu, for his very concrete help, and my wife, Jingxia Qiu, for her support, understanding and love, without which this work would have been impossible.　

Jun-Ming Xu  

( xujm@ustc.edu.cn ) 

 May 2001