Graph Theory and Interconnection Networks

Published:
Content:
Author(s):
Free Standard Shipping

Purchasing Options

Hardback
ISBN 9781420044812
Cat# 44818

$189.95

$151.96

SAVE 20%


eBook (VitalSource)
ISBN 9781420044829
Cat# E44818

$189.95

$132.97

SAVE 30%


eBook Rentals

Other eBook Options:
 

Features

  • Provides readers with mathematical logic ability, general graph background, and the ability to solve related problems
  • Presents the structures of different types of interconnection networks and analyzes the properties of these networks
  • Introduces various types of problems to demonstrate techniques
  • Explains how to use graph theory to solve interconnection related problems and to expand research abilities
  • Summary

    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.

    Table of 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