Hsu / Lin Graph Theory and Interconnection Networks

Erscheinungsjahr 2008
ISBN: 978-1-4200-4482-9
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 720 Seiten

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.

Zielgruppe

Researchers and graduate students.

Autoren/Hrsg.

Hsu, Lih-Hsing

Lin, Cheng-Kuan

Fachgebiete

• Mathematik | Informatik Mathematik Operations Research Graphentheorie

Inhaltsverzeichnis

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