2nd Edition

Handbook of Product Graphs

ISBN 9781138199088
Published November 16, 2016 by CRC Press
536 Pages 75 B/W Illustrations

USD $59.95

Prices & shipping based on shipping country


Book Description

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

Graphs and Subgraphs
Paths and Cycles
Trees and Forests
Planar Graphs

Automorphisms and Invariants
Graph Invariants
The No-Homomorphism Lemma

Hypercubes and Isometric Subgraphs
Hypercubes are Sparse
Isometric Subgraphs
Median Graphs

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

Cartesian Product
Prime Factor Decompositions
Cartesian Product and Its Group
Transitive Group Action on Products
S-Prime Graphs

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

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

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
Factorizations and Nonuniqueness

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

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

Recognizing Hypercubes and Partial Cubes
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
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
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

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

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
Tournaments and the Lexicographic Product
Prime Factorings

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

Appendix: Hints and Solutions to Exercises


Author Index

Subject Index

Symbol Index

View More



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.


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