ABSTRACT

This handbook 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, this second edition presents full proofs of many important results as well as up-to-date research and conjectures. It illustrates applications of graph products in several areas and contains well over 300 exercises. Supplementary material is available on the book's website.

part I|4 pages

A Brief Introduction to Graphs and Their Products

chapter 1|10 pages

Graphs

chapter 2|12 pages

Automorphisms and Invariants

chapter 3|8 pages

Hypercubes and Isometric Subgraphs

chapter 4|14 pages

Graph Products

chapter 5|12 pages

The Four Standard Graph Products

part II|4 pages

Factorization and Cancellation

chapter 6|14 pages

Cartesian Product

chapter 7|10 pages

Strong Product

chapter 8|18 pages

Direct Product

chapter 9|8 pages

Cancellation

chapter 10|16 pages

Lexicographic Product

part III|4 pages

Isometric Embeddings

chapter 11|10 pages

The Relation Θ and Partial Cubes

chapter 12|14 pages

Median Graphs

chapter 13|8 pages

The Canonical Isometric Embedding

chapter 14|16 pages

A Dynamic Location Problem

chapter 16|10 pages

Fixed Box Theorems

part IV|4 pages

Algorithms

chapter 17|10 pages

Graph Representation and Algorithms

chapter 18|14 pages

Recognizing Hypercubes and Partial Cubes

chapter 19|8 pages

Chemical Graphs and the Wiener Index

chapter 20|10 pages

Arboricity, Squares, and Triangles

chapter 21|18 pages

Recognizing Median Graphs

chapter 23|14 pages

Factoring the Cartesian Product

part V|4 pages

Invariants

chapter 25|10 pages

Connectivity

chapter 26|24 pages

Coloring and Hedetniemi’s Conjecture

chapter 27|14 pages

Independence Number and Shannon Capacity

chapter 28|12 pages

Domination and Vizing’s Conjecture

chapter 29|10 pages

Cycle Spaces and Bases

chapter 30|18 pages

Selected Results

part VI|4 pages

Related Concepts

chapter 31|22 pages

Infinite Graphs

chapter 32|8 pages

Products of Digraphs

chapter 33|14 pages

Near Products