2nd Edition
Handbook of Product Graphs
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.
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
Biography
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