Handbook of Product Graphs, 2nd Edition

Handbook of Product Graphs, 2nd Edition

by Richard Hammack, Wilfried Imrich, Sandi Klavžar
Released June 2011
Publisher(s): CRC Press
ISBN: 9781439813058

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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.

Table of contents

  1. Cover
  2. Half Title
  3. Series Editor
  4. Title Page
  5. Copyright Page
  6. Table of Contents (1/2)
  7. Table of Contents (2/2)
  8. Preface
  9. Foreword (1/2)
  10. Foreword (2/2)
  11. I: A Brief Introduction to Graphs and Their Products
    1. 1: Graphs
      1. 1.1 Graphs and Subgraphs
      2. 1.2 Paths and Cycles
      3. 1.3 Trees and Forests
      4. 1.4 Planar Graphs
    2. 2: Automorphisms and Invariants
      1. 2.1 Automorphisms
      2. 2.2 Vertex-Transitivity
      3. 2.3 Graph Invariants
      4. 2.4 The No-Homomorphism Lemma
    3. 3: Hypercubes and Isometric Subgraphs
      1. 3.1 Hypercubes are Sparse
      2. 3.2 Isometric Subgraphs
      3. 3.3 Median Graphs
      4. 3.4 Retracts
    4. 4: Graph Products
      1. 4.1 Three Fundamental Products
      2. 4.2 Commutativity, Associativity, and Multiple Factors
      3. 4.3 Projections and Layers
      4. 4.4 Classification of Products (1/2)
      5. 4.4 Classification of Products (2/2)
    5. 5: The Four Standard Graph Products
      1. 5.1 The Cartesian Product
      2. 5.2 The Strong Product
      3. 5.3 The Direct Product
      4. 5.4 The Lexicographic Product
  12. II: Factorization and Cancellation
    1. 6: Cartesian Product
      1. 6.1 Prime Factor Decompositions
      2. 6.2 Cartesian Product and Its Group
      3. 6.3 Transitive Group Action on Products
      4. 6.4 Cancellation
      5. 6.5 S-Prime Graphs
    2. 7: Strong Product
      1. 7.1 Basic Properties and S-Thin Graphs
      2. 7.2 Cliques and The Extraction of Complete Factors
      3. 7.3 Unique Prime Factorization for Connected Graphs
      4. 7.4 Automorphisms
    3. 8: Direct Product
      1. 8.1 Nonuniqueness of Prime Factorization
      2. 8.2 R-Thin Graphs
      3. 8.3 The Cartesian Skeleton
      4. 8.4 Factoring Connected, Nonbipartite, R-Thin Graphs
      5. 8.5 Factoring Connected, Nonbipartite Graphs
      6. 8.6 Automorphisms
      7. 8.7 Applications to the Strong Product
    4. 9: Cancellation
      1. 9.1 Cancellation for the Strong Product
      2. 9.2 Cancellation for the Direct Product
      3. 9.3 Anti-Automorphisms and Factorials
      4. 9.4 Graph Exponentiation
    5. 10: Lexicographic Product
      1. 10.1 Basic Properties
      2. 10.2 Self-Complementarity and Cancellation Properties
      3. 10.3 Commutativity
      4. 10.4 Factorizations and Nonuniqueness
      5. 10.5 Automorphisms (1/2)
      6. 10.5 Automorphisms (2/2)
  13. III: Isometric Embeddings
    1. 11: The Relation Θ and Partial Cubes
      1. 11.1 Definition and Basic Properties of Θ
      2. 11.2 Characterizations of Partial Cubes
      3. 11.3 Cubic Partial Cubes
      4. 11.4 Scale Embeddings into Hypercubes
    2. 12: Median Graphs
      1. 12.1 Mulder’s Convex Expansion
      2. 12.2 Inequalities for Median Graphs and Partial Cubes
      3. 12.3 Median Graphs as Retracts
      4. 12.4 A Fixed Cube Theorem
      5. 12.5 Median Networks in Human Genetics
    3. 13: The Canonical Isometric Embedding
      1. 13.1 The Embedding and Its Properties
      2. 13.2 The Relation Θ and the Cartesian Product
      3. 13.3 Automorphisms of Canonical Embeddings
    4. 14: A Dynamic Location Problem
      1. 14.1 Hamming Graphs
      2. 14.2 Graphs with Finite Windex
      3. 14.3 Quasi-Median Graphs and Generalizations
      4. 14.4 Graphs with Finite Windex are Quasi-Median Graphs (1/2)
      5. 14.4 Graphs with Finite Windex are Quasi-Median Graphs (2/2)
    5. 15: Isometries in Strong Products and Product Dimensions
      1. 15.1 Strong Isometric Dimension
      2. 15.2 Retracts of Strong Products
      3. 15.3 Other Product Graph Dimensions
    6. 16: Fixed Box Theorems
      1. 16.1 Gated Subgraphs and Median Functions
      2. 16.2 A Fixed Box Theorem for Median Function-Closed Graphs
      3. 16.3 Feder-Tardif’s Fixed Box Theorems
      4. 16.4 Fixed Points of Several Nonexpansive Mappings
  14. IV: Algorithms
    1. 17: Graph Representation and Algorithms
      1. 17.1 Time and Space Complexity
      2. 17.2 Adjacency List
      3. 17.3 Breadth-First Search
      4. 17.4 Adjacency Matrix
    2. 18: Recognizing Hypercubes and Partial Cubes
      1. 18.1 Hypercubes
      2. 18.2 Partial Cubes
      3. 18.3 Efficient Computation of
      4. 18.4 Recognizing Partial Cubes in Quadratic Time (1/2)
      5. 18.4 Recognizing Partial Cubes in Quadratic Time (2/2)
    3. 19: Chemical Graphs and the Wiener Index
      1. 19.1 Benzenoid Graphs as Partial Cubes
      2. 19.2 The Wiener Index of Benzenoid Graphs in Linear Time
      3. 19.3 The Wiener Index via the Canonical Isometric Embedding
    4. 20: Arboricity, Squares, and Triangles
      1. 20.1 Arboricity
      2. 20.2 Listing Squares and Triangles (1/2)
      3. 20.2 Listing Squares and Triangles (2/2)
    5. 21: Recognizing Median Graphs
      1. 21.1 A Simple Algorithm
      2. 21.2 A Fast Algorithm (1/2)
      3. 21.2 A Fast Algorithm (2/2)
      4. 21.3 Triangle-Free Graphs and Median Graphs (1/2)
      5. 21.3 Triangle-Free Graphs and Median Graphs (2/2)
    6. 22: Recognizing Partial Hamming Graphs and Quasi-Median Graphs
      1. 22.1 Hamming Graphs and Partial Hamming Graphs
      2. 22.2 Quasi-Median Graphs
      3. 22.3 Computing the Windex
    7. 23: Factoring the Cartesian Product
      1. 23.1 Product Relation
      2. 23.2 A Simple Algorithm
      3. 23.3 Coordinatization
      4. 23.4 Factorization in O(m log n) Time (1/2)
      5. 23.4 Factorization in O(m log n) Time (2/2)
      6. 23.5 Factorization in Linear Time and Space
    8. 24: Recognizing Direct, Strong, and Lexicographic Products
      1. 24.1 Direct Product
      2. 24.2 Strong Product
      3. 24.3 Factoring Thin Graphs
      4. 24.4 Factoring Non-Thin Graphs
      5. 24.5 Lexicographic Product
  15. V: Invariants
    1. 25: Connectivity
      1. 25.1 Cartesian Product
      2. 25.2 Critically Connected Graphs and The Lexicographic Product
      3. 25.3 Strong and Direct Products
    2. 26: Coloring and Hedetniemi’s Conjecture
      1. 26.1 Product Coloring
      2. 26.2 Bounds and Three Applications
      3. 26.3 Fractional and Circular Chromatic Number
      4. 26.4 Hedetniemi’s Conjecture
      5. 26.5 Hedetniemi’s Conjecture for 4-Chromatic Graphs
      6. 26.6 Circular and Fractional Version of Hedetniemi’s Conjecture
    3. 27: Independence Number and Shannon Capacity
      1. 27.1 Shannon Capacity
      2. 27.2 Independence in Direct Products
      3. 27.3 Independence in Cartesian Products
    4. 28: Domination and Vizing’s Conjecture
      1. 28.1 Vizing’s Conjecture
      2. 28.2 Clark and Suen’s Approach
      3. 28.3 Fractional Version of Vizing’s Conjecture
      4. 28.4 Domination in Direct Products
    5. 29: Cycle Spaces and Bases
      1. 29.1 The Cycle Space of a Graph
      2. 29.2 Minimum Cycle Bases for Cartesian and Strong Products
      3. 29.3 Minimum Cycle Bases for the Lexicographic Product
      4. 29.4 Minimum Cycle Bases for the Direct Product
    6. 30: Selected Results
      1. 30.1 One-Factorization and Edge-Coloring
      2. 30.2 Hamilton Cycles and Hamiltonian Decompositions
      3. 30.3 Clique Minors in Cartesian Products
      4. 30.4 Reconstruction, Topological Embeddings, and Flows
      5. 30.5 Modeling Complex Networks
  16. VI: Related Concepts
    1. 31: Infinite Graphs
      1. 31.1 Growth Rate and Ends
      2. 31.2 Free Product
      3. 31.3 Transitive Median Graphs with Finite Blocks
      4. 31.4 Two-Ended Median Graphs
      5. 31.5 Cartesian Product
      6. 31.6 Strong and Direct Product
      7. 31.7 Lexicographic Product
    2. 32: Products of Digraphs
      1. 32.1 Definitions
      2. 32.2 Connectedness
      3. 32.3 Tournaments and The Lexicographic Product
      4. 32.4 Prime Factorings
      5. 32.5 Cancellation
    3. 33: Near Products
      1. 33.1 Graph Bundles
      2. 33.2 Approximate Graph Products
      3. 33.3 Graph Spectra
      4. 33.4 Zig-Zag Product
  17. Appendix: Hints and Solutions to Exercises (1/5)
  18. Appendix: Hints and Solutions to Exercises (2/5)
  19. Appendix: Hints and Solutions to Exercises (3/5)
  20. Appendix: Hints and Solutions to Exercises (4/5)
  21. Appendix: Hints and Solutions to Exercises (5/5)
  22. Bibliography (1/7)
  23. Bibliography (2/7)
  24. Bibliography (3/7)
  25. Bibliography (4/7)
  26. Bibliography (5/7)
  27. Bibliography (6/7)
  28. Bibliography (7/7)
  29. Author Index (1/2)
  30. Author Index (2/2)
  31. Subject Index (1/2)
  32. Subject Index (2/2)
  33. Symbol Index
  34. Back Cover

Product information

  • Title: Handbook of Product Graphs, 2nd Edition
  • Author(s): Richard Hammack, Wilfried Imrich, Sandi Klavžar
  • Release date: June 2011
  • Publisher(s): CRC Press
  • ISBN: 9781439813058