组合网络理论(英文版）

This book provides the most basic combinatorial problems and well-established theory in design and analysis of the topological structure of interconnection networks in the graph-theoretic language.It covers the basic methods of network design,several well-known networks such as hypercubes,de Bruijn digraphs,Kautz digraphs,double loop,and the newest parameters to measure performance of networks such as forwarding indices of a routing,Menger number,Rabin number,fault-tolerant diameter,wide-diameter,generalized dominating number,and restricted connectivity.It will be of significant interest to researchers and practitioners working in design and analysis of networks,particularly to undergraduates and postgraduates specializing in computer science and applied mathematics. Xu Junming is a Professor at School of Mathematical Sciences,the University of Science and Technology of China(USTC),a fellow of Operations Research Society of China,and Commission on Combinatorics and Graph Theory in China.His research interest is combinatorics and graph theory,in particular,combinatorial problems of interconnection networks,has published more than 200 research papers.

Preface

Part Ⅰ Networks and Graphs

Chapter 1 Fundamentals of Networks and Graphs

1.1 Graphs and Networks

1.2 Basic Concepts and Notations

1.3 Trees and Planar Graphs

1.4 Transmission Delay and Diameter

1.5 Fault Tolerance and Connectivity

1.6 Embedding and Routings

1.7 Basic Principles of Network Design

Exercises

Chapter 2 Symmetry of Graphs or Networks

2.1 Fundamentals on Groups

2.2 Vertex-Transitive Graphs

2.3 Edge-Transitive Graphs

2.4 Atoms of Graphs

2.5 Connectivity of Transitive Graphs

Exercises

Part Ⅱ Basic Methods of Network Designs

Chapter 3 Line Graphical Methods

3.1 Line Graphs and Basic Properties

3.2 Basic Properties of Line Digraphs

3.3 Iterated Line Graphs

3.4 Connectivity of Line Graphs

Exercises

Chapter 4 Cayley Methods

4.1 Cayley Graphs

4.2 Transitivity of Cayley Graphs

4.3 Atoms and Connectivity of Cayley Graphs

4.4 Vertex-Transitive Graphs with Prime Order

Exercises

Chapter 5 Cartesian Product Methods

5.1 Cartesian Product of Graphs

5.2 Diameter and Connectivity

5.3 Other Properties of Cartesian Products

5.4 Generalized Cartesian Products

Exercises

Chapter 6 Basic Problems in Optimal Designs

6.1 Undirected(d,k)-Graph Problems

6.2 Directed(d,k)-Graph Problems

6.3 Relations between Diameter and Connectivity

Exercises

Part Ⅲ Well-Known Topologies of Networks

Chapter 7 Hypercube Networks

7.1 Definitions and Basic Properties

7.2 Gray Codes and Cycles

7.3 Lengths of Paths

7.4 Embedding Problems

7.5 Generalized Hypercubes

7.6 Some Variations of Hypercubes

Exercises

Chapter 8 De Bruijn Networks

8.1 Definitions and Basic Properties

8.2 Uniqueness of Shortest Paths

8.3 Generalized de Bruijn Digraphs

8.4 Comparison with Hypercubes

Exercises

Chapter 9 Kautz Networks

9.1 Definitions and Basic Properties

9.2 Generalized Kautz Digraphs

9.3 Connectivity of Generalized Kautz Digraphs

Exercises

Chapter 10 Double Loop Networks

10.1 Double Loop Networks

10.2 L-Tiles in the Plane

10.3 L-Tiles and Double Loop Networks

10.4 Design of Optimal Double Loop Networks

10.5 Basic Properties of Circulant Networks

Exercises

Chapter 11 Topologies of Other Networks

11.1 Mesh Networks and Grid Networks

11.2 Pyramid Networks

11.3 Cube-Connected Cycles

11.4 Butterfly Networks

11.5 Bene* Networks

11.6 Ω Networks

11.7 Shuffle-Exchange Networks

Exercises

Part Ⅳ Fault-Tolerant Analysis of Networks

Chapter 12 Routings in Networks

12.1 Forwarding Index of Routing

12.2 Edge-Forwarding Index of Routing

12.3 Forwarding Indices of Some Graphs

12.4 Delay of Fault-Tolerant Routing

Exercises

Chapter 13 Fault-Tolerant Diameters in Networks

13.1 Diameters of Altered Graphs

13.2 Edge Fault-Tolerant Diameters

13.3 Relations between Two Diameters

13.4 Vertex Fault-Tolerant Diameters

13.5 Fault-Tolerant Diameter of Product Graphs

13.6 Fault-Tolerant Diameters of Some Networks

Exercises

Chapter 14 Menger-Type Problems in Parallel Systems

14.1 Menger-Type Problems

14.2 Bounded Menger Number and Connectivity

14.3 Bounded Edge-Connectivity

14.4 Rabin Numbers of Networks

Exercises

Chapter 15 Wide-Diameters of Networks

15.1 Wide-Diameter and Basic Results

15.2 Wide-Diameter of Regular Graphs

15.3 Wide-Diameter of Cartesian Products

15.4 Wide-Diameter and Independence Number

15.5 Wide-Diameter and Fault-Tolerant Diameter

15.6 Wide-Diameters of Some Networks

Exercises

Chapter 16 Generalized Independence and Domination Numbers

16.1 Generalized Independence Numbers

16.2 Generalized Domination Numbers

16.3 Distance Independence and Domination

Exercises

Chapter 17 Restricted Fault-Tolerance of Networks

17.1 Restricted Connectivity and Diameter

17.2 Restricted Edge-Connectivity

17.3 Restricted Edge-Atoms

17.4 Results on Transitive Graphs

17.5 Super Connectivity of Networks

17.6 Super Edge-Connectivity of Networks

17.7 Super Connectivity of Line Graphs

17.8 Connectivity Restricted by Degree-Conditions

17.9 Connectivity Restricted by Order-Conditions

17.10 Restricted Connectivity of Some Networks

Exercises

Bibliography

A List of Notations

Index