Product Graphs: Structure and RecognitionISBN: 9780471370390
360 pages
April 2000

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 muchneeded, 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, trianglefree graphs, and vertextransitive 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
Addressing the growing usefulness of current methods for recognizing product graphs, this new work presents a muchneeded, 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, trianglefree graphs, and vertextransitive 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
See More
Basic Concepts.
Hypercubes.
Hamming Graphs.
Cartesian Products.
Strong and Direct Products.
Lexicographic Products.
Fast Recognition Algorithms.
Invariants.
Appendices.
Bibliography.
Indexes.
Hypercubes.
Hamming Graphs.
Cartesian Products.
Strong and Direct Products.
Lexicographic Products.
Fast Recognition Algorithms.
Invariants.
Appendices.
Bibliography.
Indexes.
See More
WILFRIED IMRICH, PhD, is Professor of Applied Mathematics at Montanuniversität Leoben in Austria.
SANDI KLAVZAR, PhD, is Professor of Discrete and Computer Mathematics at the University of Maribor as well as the University of Ljubljana in Slovenia.
SANDI KLAVZAR, PhD, is Professor of Discrete and Computer Mathematics at the University of Maribor as well as the University of Ljubljana in Slovenia.
See More
"In addition to its suitability as a text for a variety of courses in mathematics or in computer science, this book should be a valuable addition to the library of any student of, or researcher in, graph theory." (Zentralblatt Math online, 2001)
"The exercises and the comprehensive and uptodate bibliography make the book an invaluable text for students and researchers alike...Imrich and Klavar have done the world a great favor by collecting all of these nice results into a cogent, readable text." (MathSciNet, 2001)
"The exercises and the comprehensive and uptodate bibliography make the book an invaluable text for students and researchers alike. Peter Winkler rightly mentions in the foreword that Imrich and Klavzar have done the world a great favor by collecting all of these nice results into a cogent, readable text." (Mathematical Reviews, Issue 2001k)
"Basic properties, invariants, recognition algorithms for graphs which are...products of graphs." (American Mathematical Monthly, November 2000)
"..a valuable addition to the library of any student of, or teacher in, graph theory." (Zentralblatt MATH, Vol. 963, 2001/13)
"this book should be a valuable addition to the library of any student of, or researcher in, graph theory." (Zentralblatt MATH, Vol. 963 No.13, 2001)
"The exercises and the comprehensive and uptodate bibliography make the book an invaluable text for students and researchers alike...Imrich and Klavar have done the world a great favor by collecting all of these nice results into a cogent, readable text." (MathSciNet, 2001)
"The exercises and the comprehensive and uptodate bibliography make the book an invaluable text for students and researchers alike. Peter Winkler rightly mentions in the foreword that Imrich and Klavzar have done the world a great favor by collecting all of these nice results into a cogent, readable text." (Mathematical Reviews, Issue 2001k)
"Basic properties, invariants, recognition algorithms for graphs which are...products of graphs." (American Mathematical Monthly, November 2000)
"..a valuable addition to the library of any student of, or teacher in, graph theory." (Zentralblatt MATH, Vol. 963, 2001/13)
"this book should be a valuable addition to the library of any student of, or researcher in, graph theory." (Zentralblatt MATH, Vol. 963 No.13, 2001)
See More