Product Graphs: Structure and Recognition

✍ Scribed by Wilfried Imrich, Sandi Klavžar

• Publisher: Wiley-Interscience
• Year: 2000
• Tongue: English
• Leaves: 374
• Edition: 1
• Category: Library

✦ Synopsis

A comprehensive introduction to the four standard products of graphs and related topics

Addressing the growing usefulness of current methods for recognizing product graphs, this new work presents a much-needed, systematic treatment of the Cartesian, strong, direct, and lexicographic products of graphs as well as graphs isometrically embedded into them. Written by two leading experts in this rapidly evolving area of combinatorics, Product Graphs: Structure and Recognition compiles and consolidates a wealth of information previously scattered throughout the literature, providing researchers in the field with ready access to numerous recent results as well as several new recognition algorithms and proofs. The authors explain all topics from the ground up and make the requisite theory and data structures easily accessible for mathematicians and computer scientists alike.

Coverage includes
* The basic algebraic and combinatorial properties ofproduct graph
* Hypercubes, median graphs, Hamming graphs, triangle-free graphs, and vertex-transitive graphs
* Colorings, automorphisms, homorphisms, domination, and the capacity of products of graphs Sample applications, including novel applications to chemical graph theory Clear connections to other areas of graph theory Figures, exercises, and hundreds of references

✦ Table of Contents

Title
Contents
Foreword
Preface
Introduction
Basic concepts
Graphs
Automorphisms and invariants
Hypercube and isometric subgraphs
The Cartesian product
Graph representations and algorithms
Exercises
Hypercubes
The Djokovic-Winkler relation
An application to chemical graphs
Mulder's convex expansion
Retracts and fixed cubes
Notes
Exercises
Hamming graphs
Canonical isometric embeddings
A dynamic location problem
Quasi-median graphs
Recognition algorithms
Notes
Exercises
Cartesian products
Prime factor decompositions
Automorphisms
Fixed box theorems
Notes
Exercises
Strong and direct products
Strong products and retracts
Factoring strong products
Direct products in Gamma and Gamma_0
Factoring direct products
Recognition of direct and strong products
Notes
Exercises
Lexicographic products
Basic algebraic properties
Factorizations and nonuniqueness
Automorphisms
Recognition complexity
Notes
Exercises
Fast recognition algorithms
Arboricity, squares, and triangles
Fast recognition of median graphs
Triangle-free graphs and median graphs
Fast recognition of Cartesian products
Notes
Exercises
Invariants
Invariants and standard products
Hedetniemi's conjecture
Coloring lexicographic products
Fractional and circular chromatic number
Shannon capacity
Vizing's conjecture
Notes
Exercises
Selected results and conjectures
One-factorizations
Hamiltonian decomposable graphs
Perfect graphs
Ultimate independence ratio
Short remarks
Exercises
Infinite graphs
Trees, partial cubes, and Hamming graphs
Cartesian products
Strong and direct products
Lexicographic products
Exercises
Other graph products
Simple products
Associative simple products
The modular product
Graph exponentiation
Exercises
Bibliography
Name Index
Subject Index
Symbol Index