536 Pages 75 B/W Illustrations
    by CRC Press

    536 Pages 75 B/W Illustrations
    by CRC Press

    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