Other eBook Options:

- 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

**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 PRODUCTSGraphs **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 CANCELLATIONCartesian 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 EMBEDDINGSThe 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

**ALGORITHMSGraph 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

**INVARIANTSConnectivity **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 CONCEPTSInfinite 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**

**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