Graph Theory and Interconnection Networks

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

ISBN: 9781420044812 | 1420044818
Cover: Hardcover
Copyright: 9/26/2008

Rent

(Recommended)

$169.95

Term

Due

Price

Semester

Dec 11

$169.95

Quarter

Nov 16

$161.45

Short Term

Oct 17

$152.96

*This item is part of an exclusive publisher rental program and requires an additional convenience fee. This fee will be reflected in the shopping bag.
Buy New

Usually Ships in 3-5 Business Days

$217.58
eBook

Available Instantly

Online: 180 Days

Downloadable: 180 Days

*To support the delivery of the digital material to you, a digital delivery fee of $3.99 will be charged on each digital item.

$60.72*

Graph theory is a powerful tool in the design, analysis, and general study of complex interconnection networks. Computer scientists and engineers universally accept that the nature of network topology makes graph theory the natural option. Despite this, most references fail to sufficiently explain graph theory's fundamental role in interconnection networks.

Preface	p. xi
Authors	p. xiii
Fundamental Concepts	p. 1
Graphs and Simple Graphs	p. 1
Matrices and Isomorphisms	p. 5
Paths and Cycles	p. 9
Vertex Degrees	p. 12
Graph Operations	p. 14
Some Basic Techniques	p. 16
Degree Sequences	p. 18
Applications on Graph Isomorphisms	p. 21
Generalized Honeycomb Tori	p. 21
Isomorphism between Cyclic-Cubes and Wrapped Butterfly Networks	p. 24
1-Edge Fault-Tolerant Design for Meshes	p. 26
Faithful 1-Edge Fault-Tolerant Graphs	p. 31
k-Edge Fault-Tolerant Designs for Hypercubes	p. 40
Distance and Diameter	p. 43
Introduction	p. 43
Diameter for Some Interconnection Networks	p. 43
Shuffle-Cubes	p. 47
Route 1(u, v)	p. 49
Moore Bound	p. 50
Star Graphs and Pancake Graphs	p. 52
Edge Congestion and Bisection Width	p. 55
Transmitting Problem	p. 57
Trees	p. 61
Basic Properties	p. 61
Breadth-First Search and Depth-First Search	p. 64
Rooted Trees	p. 65
Counting Trees	p. 68
Counting Binary Trees	p. 72
Number of Spanning Trees Contains a Certain Edge	p. 73
Embedding Problem	p. 76
Eulerian Graphs and Digraphs	p. 79
Eulerian Graphs	p. 79
Eulerian Digraphs	p. 82
Applications	p. 85
Chinese Postman Problem	p. 85
Street-Sweeping Problem	p. 86
Drum Design Problem	p. 86
Functional Cell Layout Problem	p. 87
Matchings and Factors	p. 93
Matchings	p. 93
Bipartite Matching	p. 95
Edge Cover	p. 98
Perfect Matching	p. 100
Factors	p. 103
Connectivity	p. 105
Cut and Connectivity	p. 105
2-Connected Graphs	p. 109
Menger Theorem	p. 111
An Application-Making a Road System One-Way	p. 115
Connectivity of Some Interconnection Networks	p. 117
Wide Diameters and Fault Diameters	p. 118
Superconnectivity and Super-Edge-Connectivity	p. 120
Graph Coloring	p. 125
Vertex Colorings and Bounds	p. 125
Properties of k-Critical Graphs	p. 126
Bound for Chromatic Numbers	p. 128
Girth and Chromatic Number	p. 130
Hajos' Conjecture	p. 131
Enumerative Aspects	p. 133
Homomorphism Functions	p. 136
An Application-Testing on Printed Circuit Boards	p. 137
Edge-Colorings	p. 138
Hamiltonian Cycles	p. 141
Hamiltonian Graphs	p. 141
Necessary Conditions	p. 141
Sufficient Conditions	p. 143
Hamiltonian-Connected	p. 147
Mutually Independent Hamiltonian Paths	p. 152
Diameter for Generalized Shuffle-Cubes	p. 155
Cycles in Directed Graphs	p. 158
Planar Graphs	p. 161
Planar Embeddings	p. 161
Euler's Formula	p. 165
Characterization of Planar Graphs	p. 166
Coloring of Planar Graphs	p. 167
Optimal k-Fault-Tolerant Hamiltonian Graphs	p. 171
Introduction	p. 171
Node Expansion	p. 173
Other Construction Methods	p. 180
Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of the Folded Petersen Cube Networks	p. 185
Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of the Pancake Graphs	p. 189
Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of Augmented Cubes	p. 195
Fault-Tolerant Hamiltonicity and Fault-Tolerant Hamiltonian Connectivity of the WK-Recursive Networks	p. 206
Fault-Tolerant Hamiltonicity of the Fully Connected Cubic Networks	p. 221
Optimal 1-Fault-Tolerant Hamiltonian Graphs	p. 227
Introduction	p. 227
3-Join	p. 228
Cycle Extension	p. 229
Cells for Optimal 1-Hamiltonian Regular Graphs	p. 241
Generalized Petersen Graphs	p. 249
Honeycomb Rectangular Disks	p. 259
Properties with Respect to the 3-Join	p. 262
Examples of Various Cubic Planar Hamiltonian Graphs	p. 267
A [intersection of] B [intersection of] C	p. 268
A [intersection of] B [intersection of] C	p. 268
A [intersection of] B [intersection of] C	p. 268
A [intersection of] B [intersection of] C	p. 269
A [intersection of] B [intersection of] C	p. 271
A [intersection of] B [intersection of] C	p. 272
A [intersection of] B [intersection of] C	p. 273
A [intersection of] B [intersection of] C	p. 274
Hamiltonian Properties of Double Loop Networks	p. 275
Optimal k-Fault-Tolerant Hamiltonian-Laceable Graphs	p. 285
Introduction	p. 285
Super Fault-Tolerant Hamiltonian Laceability of Hypercubes	p. 287
Super Fault-Tolerant Hamiltonian Laceability of Star Graphs	p. 289
Construction Schemes	p. 294
Cubic Hamiltonian-Laceable Graphs	p. 301
l[superscript p]-Fault-Tolerant Hamiltonian Graphs	p. 303
Spider-Web Networks	p. 303
Brother Trees	p. 312
Hamiltonian Laceability of Faulty Hypercubes	p. 318
Conditional Fault Hamiltonicity and Conditional Fault Hamiltonian Laceability of the Star Graphs	p. 327
Spanning Connectivity	p. 339
Introduction	p. 339
Spanning Connectivity of General Graphs	p. 339
Spanning Connectivity and Spanning Laceability of the Hypercube-Like Networks	p. 347
Spanning Connectivity of Crossed Cubes	p. 361
Spanning Connectivity and Spanning Laceability of the Enhanced Hypercube Networks	p. 374
Spanning Connectivity of the Pancake Graphs	p. 391
Spanning Laceability of the Star Graphs	p. 404
Spanning Fan-Connectivity and Spanning Pipe-Connectivity of Graphs	p. 410
Cubic 3-Connected Graphs and Cubic 3-Laceable Graphs	p. 417
Properties of Cubic 3*-Connected Graphs	p. 417
Examples of Cubic Super 3*-Connected Graphs	p. 419
Counterexamples of 3*-Connected Graphs	p. 426
Properties of Cubic 3*-Laceable Graphs	p. 430
Examples of Cubic Hyper 3*-Laceable Graphs	p. 431
Counterexamples of 3*-Laceable Graphs	p. 447
Spanning Diameter	p. 449
Introduction	p. 449
Spanning Diameter for the Star Graphs	p. 449
Spanning Diameter of Hypercubes	p. 465
Spanning Diameter for Some (n, k)-Star Graphs	p. 474
Pancyclic and Panconnected Property	p. 479
Introduction	p. 479
Bipanconnected and Bipancyclic Properties of Hypercubes	p. 480
Edge Fault-Tolerant Bipancyclic Properties of Hypercubes	p. 485
Panconnected and Pancyclic Properties of Augmented Cubes	p. 489
Comparison between Panconnected and Panpositionable Hamiltonian	p. 500
Bipanpositionable Bipancyclic Property of Hypercube	p. 504
Mutually Independent Hamiltonian Cycles	p. 509
Introduction	p. 509
Mutually Independent Hamiltonian Cycles on Some Graphs	p. 510
Mutually Independent Hamiltonian Cycles of Hypercubes	p. 512
Mutually Independent Hamiltonian Cycles of Pancake Graphs	p. 518
Mutually Independent Hamiltonian Cycles of Star Graphs	p. 524
Fault-Free Mutually Independent Hamiltonian Cycles in a Faulty Hypercube	p. 526
Fault-Free Mutually Independent Hamiltonian Cycles in Faulty Star Graphs	p. 530
Orthogonality for Sets of Mutually Independent Hamiltonian Cycles	p. 543
Mutually Independent Hamiltonian Paths	p. 545
Introduction	p. 545
Mutually Independent Hamiltonian Laceability for Hypercubes	p. 545
Mutually Independent Hamiltonian Laceability for Star Graphs	p. 550
Mutually Independent Hamiltonian Connectivity for (n, k)-Star Graphs	p. 555
Cubic 2-Independent Hamiltonian-Connected Graphs	p. 575
Examples of Cubic 2-Independent Hamiltonian-Connected Graphs That Are Super 3*-Connected	p. 576
Examples of Super 3*-Connected Graphs That Are Not Cubic 2-Independent Hamiltonian-Connected	p. 579
Example of a Cubic 2-Independent Hamiltonian-Connected Graph That Is Not Super 3*-Connected	p. 580
Example of a Cubic 1-Fault-Tolerant Hamiltonian Graph That Is Hamiltonian-Connected but Not Cubic 2-Independent Hamiltonian-Connected or Super 3*-Connected	p. 581
Topological Properties of Butterfly Graphs	p. 585
Introduction	p. 585
Cycle Embedding in Faulty Butterfly Graphs	p. 590
Spanning Connectivity for Butterfly Graphs	p. 607
Mutually Independent Hamiltonicity for Butterfly Graphs	p. 616
Diagnosis of Multiprocessor Systems	p. 625
Introduction	p. 625
Diagnosis Models	p. 625
PMC Model	p. 626
Comparison Model	p. 628
Diagnosability of the Matching Composition Networks	p. 631
Diagnosability of the Matching Composition Networks under the PMC Model	p. 632
Diagnosability of the Matching Composition Networks under the Comparison Model	p. 632
Diagnosability of Cartesian Product Networks	p. 637
Diagnosability of Cartesian Product Networks under the PMC Model	p. 638
Diagnosability of Cartesian Product Networks under the Comparison Model	p. 639
Diagnosability of t-Connected Networks	p. 639
Diagnosability of Homogeneous Product Networks	p. 641
Diagnosability of Heterogeneous Product Networks	p. 644
Strongly t-Diagnosable Systems	p. 645
Strongly t-Diagnosable Systems in the Matching Composition Networks	p. 649
Conditional Diagnosability	p. 652
Conditional Diagnosability of Q[subscript n] under the PMC Model	p. 653
Conditional Diagnosability of Q[subscript n] under the Comparison Model	p. 658
Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the Comparison Diagnosis Model	p. 666
Cayley Graphs Generated by Transposition Trees	p. 666
Conditional Diagnosability	p. 668
Local Diagnosability	p. 670
Strongly Local-Diagnosable Property	p. 675
Conditional Fault Local Diagnosability	p. 679
References	p. 687
Index	p. 703
Table of Contents provided by Ingram. All Rights Reserved.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Graph Theory and Interconnection Networks

Summary

Table of Contents

Supplemental Materials