Handbook of Product Graphs: 2nd Edition (Hardback) book cover

Handbook of Product Graphs

2nd Edition

By Richard Hammack, Wilfried Imrich, Sandi Klavžar

CRC Press

536 pages | 75 B/W Illus.

Purchasing Options:$ = USD
Paperback: 9781138199088
pub: 2016-11-16
SAVE ~$12.99
$64.95
$51.96
x
Hardback: 9781439813041
pub: 2011-06-06
SAVE ~$33.00
$165.00
$132.00
x
eBook (VitalSource) : 9780429130595
pub: 2011-06-06
from $28.98


FREE Standard Shipping!

Description

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.

Reviews

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

Table of Contents

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

About the Authors

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.

About the Series

Discrete Mathematics and Its Applications

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COM046000
COMPUTERS / Operating Systems / General
MAT000000
MATHEMATICS / General
MAT036000
MATHEMATICS / Combinatorics