# Graph Theory and Interconnection Networks

#### By **Lih-Hsing Hsu**, **Cheng-Kuan Lin**

CRC Press – 2008 – 720 pages

CRC Press – 2008 – 720 pages

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**

Graphs and Simple Graphs

Matrices and Isomorphisms

Paths and Cycles

Vertex Degrees

Graph Operations

Some Basic Techniques

Degree Sequences

**Applications on Graph Isomorphisms**

Generalized Honeycomb Tori

Isomorphism between Cyclic-Cubes and Wrapped Butterfly Networks

1-Edge Fault-Tolerant Design for Meshes

Faithful 1-Edge Fault-Tolerant Graphs

k-Edge Fault-Tolerant Designs for Hypercubes

**Distance and Diameter**

Diameter for Some Interconnection Networks

Shuffle-Cubes

Moore Bound

Star Graphs and Pancake Graphs

Edge Congestion and Bisection Width

Transmitting Problem

**Trees**

Basic Properties

Breadth-First Search and Depth-First Search

Rooted Trees

Counting Trees

Counting Binary Trees

Number of Spanning Trees Contains a Certain Edge

Embedding Problem

**Eulerian Graphs and Digraphs**

Eulerian Graphs

Eulerian Digraphs

Applications

**Matchings and Factors**

Matchings

Bipartite Matching

Edge Cover

Perfect Matching

Factors

**Connectivity**

Cut and Connectivity

2-Connected Graphs

Menger Theorem

An Application—Making a Road System One-Way

Connectivity of Some Interconnection Networks

Wide Diameters and Fault Diameters

Superconnectivity and Super-Edge-Connectivity

**Graph Coloring**

Vertex Colorings and Bounds

Properties of k-Critical Graphs

Bound for Chromatic Numbers

Girth and Chromatic Number

Hajós’ Conjecture

Enumerative Aspects

Homomorphism Functions

An Application—Testing on Printed Circuit Boards

Edge-Colorings

**Hamiltonian Cycles**

Hamiltonian Graphs

Necessary Conditions

Sufficient Conditions

Hamiltonian-Connected

Mutually Independent Hamiltonian Paths

Diameter for Generalized Shuffle-Cubes

Cycles in Directed Graphs

**Planar Graphs**

Planar Embeddings

Euler’s Formula

Characterization of Planar Graphs

Coloring of Planar Graphs

**Optimal k-Fault-Tolerant Hamiltonian Graphs**

Node Expansion

Other Construction Methods

Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of the Folded Petersen Cube Networks

Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of the Pancake Graphs

Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of Augmented Cubes

Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of the WK-Recursive Networks

Fault-Tolerant Hamiltonicity of the Fully Connected Cubic Networks

**Optimal 1-Fault-Tolerant Hamiltonian Graphs**

3-Join

Cycle Extension

Cells for Optimal 1-Hamiltonian Regular Graphs

Generalized Petersen Graphs

Honeycomb Rectangular Disks

Properties with Respect to the 3-Join

Examples of Various Cubic Planar Hamiltonian Graphs

Hamiltonian Properties of Double Loop Networks

**Optimal k-Fault-Tolerant Hamiltonian-Laceable Graphs**

Super Fault-Tolerant Hamiltonian Laceability of Hypercubes

Super Fault-Tolerant Hamiltonian Laceability of Star Graphs

Construction Schemes

Cubic Hamiltonian-Laceable Graphs

1p-Fault-Tolerant Hamiltonian Graphs

Hamiltonian Laceability of Faulty Hypercubes

Conditional Fault Hamiltonicity and Conditional Fault Hamiltonian Laceability of the Star Graphs

**Spanning Connectivity**

Spanning Connectivity of General Graphs

Spanning Connectivity and Spanning Laceability of the Hypercube-Like Networks

Spanning Connectivity of Crossed Cubes

Spanning Connectivity and Spanning Laceability of the Enhanced Hypercube Networks

Spanning Connectivity of the Pancake Graphs

Spanning Laceability of the Star Graphs

Spanning Fan-Connectivity and Spanning Pipe-Connectivity of Graphs

**Cubic 3*-Connected Graphs and Cubic 3*-Laceable Graphs**

Properties of Cubic 3*-Connected Graphs

Examples of Cubic Super 3*-Connected Graphs

Counterexamples of 3*-Connected Graphs

Properties of Cubic 3*-Laceable Graphs

Examples of Cubic Hyper 3*-Laceable Graphs

Counterexamples of 3*-Laceable Graphs

**Spanning Diameter**

Spanning Diameter for the Star Graphs

Spanning Diameter of Hypercubes

Spanning Diameter for Some (n, k)-Star Graphs

**Pancyclic and Panconnected Property**

Bipanconnected and Bipancyclic Properties of Hypercubes

Edge Fault-Tolerant Bipancyclic Properties of Hypercubes

Panconnected and Pancyclic Properties of Augmented Cubes

Comparison between Panconnected and Panpositionable Hamiltonian

Bipanpositionable Bipancyclic Property of Hypercube

**Mutually Independent Hamiltonian Cycles**

Mutually Independent Hamiltonian Cycles on Some Graphs

Mutually Independent Hamiltonian Cycles of Hypercubes

Mutually Independent Hamiltonian Cycles of Pancake Graphs

Mutually Independent Hamiltonian Cycles of Star Graphs

Fault-Free Mutually Independent Hamiltonian Cycles in a Faulty Hypercube

Fault-Free Mutually Independent Hamiltonian Cycles in Faulty Star Graphs

Orthogonality for Sets of Mutually Independent Hamiltonian Cycles

**Mutually Independent Hamiltonian Paths**

Mutually Independent Hamiltonian Laceability for Hypercubes

Mutually Independent Hamiltonian Laceability for Star Graphs

Mutually Independent Hamiltonian Connectivity for (n, k)-Star Graphs

Cubic 2-Independent Hamiltonian-Connected Graphs

**Topological Properties of Butterfly Graphs**

Cycle Embedding in Faulty Butterfly Graphs

Spanning Connectivity for Butterfly Graphs

Mutually Independent Hamiltonicity for Butterfly Graphs

**Diagnosis of Multiprocessor Systems**

Diagnosis Models

Diagnosability of the Matching Composition Networks

Diagnosability of Cartesian Product Networks

Strongly t-Diagnosable Systems

Conditional Diagnosability

Conditional Diagnosability of Qn under the Comparison Model

Local Diagnosability

References

Name: Graph Theory and Interconnection Networks (Hardback) – CRC Press

Description: By Lih-Hsing Hsu, Cheng-Kuan Lin. 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...

Categories: Mathematics & Statistics for Engineers, Combinatorics, Computer Engineering