Skip to Content

Graph Theory and Interconnection Networks

By Lih-Hsing Hsu, Cheng-Kuan Lin

CRC Press – 2008 – 720 pages

Purchasing Options:

  • Add to CartHardback: $189.95
    978-1-42-004481-2
    September 26th 2008

Description

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.

Contents

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