Handbook of Product Graphs, Second Edition

Handbook of Product Graphs, Second Edition

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

Purchasing Options

Hardback
$109.95
ISBN 9781439813041
Cat# K10662
Add to cart
eBook (VitalSource)
$109.95 $76.97
ISBN 9781439813058
Cat# KE10613
Add to cart
SAVE 30%
eBook Rentals
Other eBook Options:
 
 

Features

  • Offers a thorough introduction to the Cartesian, strong, direct, and lexicographic products and their subgraphs
  • Presents numerous new results and algorithms, including some that solve long-standing questions
  • Illustrates applications of graph products in several areas, including dynamic location theory, chemistry, human genetics, structural mechanics, and graph visualization
  • Describes the dot product, the random dot product, and applications to the generation of random graphs with prescribed properties
  • Applies the free product of graphs to infinite median graphs
  • Defines the zig-zag and replacement products
  • Contains well over 300 exercises, with hints or full solutions in the appendix
  • Provides sample implementations of selected algorithms and other useful information on the book’s website

Summary

Handbook of Product Graphs, Second Edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures.

Results and Algorithms New to the Second Edition:

  • Cancellation results
  • A quadratic recognition algorithm for partial cubes
  • Results on the strong isometric dimension
  • Computing the Wiener index via canonical isometric embedding
  • Connectivity results
  • A fractional version of Hedetniemi’s conjecture
  • Results on the independence number of Cartesian powers of vertex-transitive graphs
  • Verification of Vizing’s conjecture for chordal graphs
  • Results on minimum cycle bases
  • Numerous selected recent results, such as complete minors and nowhere-zero flows

The second edition of this classic handbook provides a thorough introduction to the subject and an extensive survey of the field. The first three parts of the book cover graph products in detail. The authors discuss algebraic properties, such as factorization and cancellation, and explore interesting and important classes of subgraphs. The fourth part presents algorithms for the recognition of products and related classes of graphs. The final two parts focus on graph invariants and infinite, directed, and product-like graphs. Sample implementations of selected algorithms and other information are available on the book’s website, which can be reached via the authors’ home pages.

Table of Contents

A BRIEF INTRODUCTION TO GRAPHS AND THEIR PRODUCTS
Graphs
Graphs and Subgraphs
Paths and Cycles
Trees and Forests
Planar Graphs

Automorphisms and Invariants
Automorphisms
Vertex-Transitivity
Graph Invariants
The No-Homomorphism Lemma

Hypercubes and Isometric Subgraphs
Hypercubes are Sparse
Isometric Subgraphs
Median Graphs
Retracts

Graph Products
Three Fundamental Products
Commutativity, Associativity, and Multiple Factors
Projections and Layers
Classification of Products

The Four Standard Graph Products
The Cartesian Product
The Strong Product
The Direct Product
The Lexicographic Product

FACTORIZATION AND CANCELLATION
Cartesian Product
Prime Factor Decompositions
Cartesian Product and Its Group
Transitive Group Action on Products
Cancellation
S-Prime Graphs

Strong Product
Basic Properties and S-Thin Graphs
Cliques and the Extraction of Complete Factors
Unique Prime Factorization for Connected Graphs
Automorphisms

Direct Product
Nonuniqueness of Prime Factorization
R-Thin Graphs
The Cartesian Skeleton
Factoring Connected, Nonbipartite, R-Thin Graphs
Factoring Connected, Nonbipartite Graphs
Automorphisms
Applications to the Strong Product

Cancellation
Cancellation for the Strong Product
Cancellation for the Direct Product
Anti-Automorphisms and Factorials
Graph Exponentiation

Lexicographic Product
Basic Properties
Self-Complementarity and Cancellation Properties
Commutativity
Factorizations and Nonuniqueness
Automorphisms

ISOMETRIC EMBEDDINGS
The Relation Θ and Partial Cubes
Definition and Basic Properties of Θ
Characterizations of Partial Cubes
Cubic Partial Cubes
Scale Embeddings into Hypercubes

Median Graphs
Mulder’s Convex Expansion
Inequalities for Median Graphs and Partial Cubes
Median Graphs as Retracts
A Fixed Cube Theorem
Median Networks in Human Genetics

The Canonical Isometric Embedding
The Embedding and Its Properties
The Relation Θ and the Cartesian Product
Automorphisms of Canonical Embeddings

A Dynamic Location Problem
Hamming Graphs
Graphs with Finite Windex
Quasi-Median Graphs and Generalizations
Graphs with Finite Windex are Quasi-Median Graphs

Isometries in Strong Products and Product Dimensions
Strong Isometric Dimension
Retracts of Strong Products
Other Product Graph Dimensions

Fixed Box Theorems
Gated Subgraphs and Median Functions
A Fixed Box Theorem for Median Function-Closed Graphs
Feder-Tardif’s Fixed Box Theorems
Fixed Points of Several Nonexpansive Mappings

ALGORITHMS
Graph Representation and Algorithms
Time and Space Complexity
Adjacency List
Breadth-First Search
Adjacency Matrix

Recognizing Hypercubes and Partial Cubes
Hypercubes
Partial Cubes
Efficient Computation of Θ*
Recognizing Partial Cubes in Quadratic Time

Chemical Graphs and the Wiener Index
Benzenoid Graphs as Partial Cubes
The Wiener Index of Benzenoid Graphs in Linear Time
The Wiener Index via the Canonical Isometric Embedding

Arboricity, Squares, and Triangles
Arboricity
Listing Squares and Triangles

Recognizing Median Graphs
A Simple Algorithm
A Fast Algorithm
Triangle-Free Graphs and Median Graphs

Recognizing Partial Hamming Graphs and Quasi-Median Graphs
Hamming Graphs and Partial Hamming Graphs
Quasi-Median Graphs
Computing the Windex

Factoring the Cartesian Product
Product Relation
A Simple Algorithm
Coordinatization
Factorization in O(m log n) Time
Factorization in Linear Time and Space

Recognizing Direct, Strong, and Lexicographic Products
Direct Product
Strong Product
Factoring Thin Graphs
Factoring Non-Thin Graphs
Lexicographic Product

INVARIANTS
Connectivity
Cartesian Product
Critically Connected Graphs and the Lexicographic Product
Strong and Direct Products

Coloring and Hedetniemi’s Conjecture
Product Coloring
Bounds and Three Applications
Fractional and Circular Chromatic Number
Hedetniemi’s Conjecture
Hedetniemi’s Conjecture for 4-Chromatic Graphs
Circular and Fractional Version of Hedetniemi’s Conjecture

Independence Number and Shannon Capacity
Shannon Capacity
Independence in Direct Products
Independence in Cartesian Products

Domination and Vizing’s Conjecture
Vizing’s Conjecture
Clark and Suen’s Approach
Fractional Version of Vizing’s Conjecture
Domination in Direct Products

Cycle Spaces and Bases
The Cycle Space of a Graph
Minimum Cycle Bases for Cartesian and Strong Products
Minimum Cycle Bases for the Lexicographic Product
Minimum Cycle Bases for the Direct Product

Selected Results
One-Factorization and Edge-Coloring
Hamilton Cycles and Hamiltonian Decompositions
Clique Minors in Cartesian Products
Reconstruction, Topological Embeddings, and Flows
Modeling Complex Networks

RELATED CONCEPTS
Infinite Graphs
Growth Rate and Ends
Free Product
Transitive Median Graphs with Finite Blocks
Two-Ended Median Graphs
Cartesian Product
Strong and Direct Product
Lexicographic Product

Products of Digraphs
Definitions
Connectedness
Tournaments and the Lexicographic Product
Prime Factorings
Cancellation

Near Products
Graph Bundles
Approximate Graph Products
Graph Spectra
Zig-Zag Product

Appendix: Hints and Solutions to Exercises

Bibliography

Author Index

Subject Index

Symbol Index

Author Bio(s)

Richard Hammack is an associate professor in the Department of Mathematics and Applied Mathematics at Virginia Commonwealth University. Dr. Hammack is a member of the American Mathematical Society, the Mathematical Association of America, and the Institute of Combinatorics and its Applications. He earned a Ph.D. in mathematics from the University of North Carolina at Chapel Hill.

Wilfried Imrich is professor emeritus in the Department of Mathematics and Information Technology at Montanuniversität Leoben. His research interests include the structure of finite and infinite graphs, graph automorphisms, combinatorial group theory, and graph algorithms. Dr. Imrich earned a Ph.D. from the University of Vienna.

Sandi Klavžar is a professor in the Faculty of Mathematics and Physics at the University of Ljubljana and in the Faculty of Natural Sciences and Math at the University of Maribor. Dr. Klavžar is an editorial board member of Ars Mathematica Contemporanea, Asian-European Journal of Mathematics, Discussiones Mathematicae Graph Theory, European Journal of Combinatorics, and MATCH Communications in Mathematical and in Computer Chemistry.

Editorial Reviews

It is my pleasure to introduce you to the marvelous world of graph products, as presented by three experts in a hugely expanded and updated edition of the classic by Imrich and Klavžar. This version, really a new book (thirty-three chapters, up from nine!), contains streamlined proofs, new applications, solutions to conjectures (such as Vizing’s conjecture for chordal graphs), and new results in graph minors and flows. Every graph theorist, most combinatorialists, and many other mathematicians will want this volume in their collection. …The authors have paid careful attention to algorithmic issues (indeed, many of the most attractive algorithms are products of their own research). Readers will find a gentle but incisive introduction to graph algorithms here, and a persuasive lesson on the insights to be gained by algorithmic analysis. In sum—and product—Hammack, Imrich, and Klavžar have put together a world of elegant and useful results in a cogent, readable text. The old book was already a delight, and you will want the new one in an accessible place on your bookshelf.
—From the Foreword by Peter Winkler, Dartmouth College, Hanover, New Hampshire, USA

 
Textbooks
Other CRC Press Sites
Featured Authors
STAY CONNECTED
Facebook Page for CRC Press Twitter Page for CRC Press You Tube Channel for CRC Press LinkedIn Page for CRC Press Google Plus Page for CRC Press Pinterest Page for CRC Press
Sign Up for Email Alerts
© 2014 Taylor & Francis Group, LLC. All Rights Reserved. Privacy Policy | Cookie Use | Shipping Policy | Contact Us