×

Topics in graph theory. Graphs and their Cartesian product. (English) Zbl 1156.05001

Wellesley, MA: A K Peters (ISBN 978-1-56881-429-2/hbk). xiv, 205 p. (2008).
The main topic of this book is graph products and their subgraphs (Hamming graphs, hypercubes, prisms and other classes of graphs). It includes problems from coding theory, frequency assignment, and mathematical chemistry, giving the reader a flavor of the variety of the applications.
The book is divided into five parts. Part I (Cartesian products) is a short introduction to the Cartesian product and applications to Hamming and Tower of Hanoi graphs. Part II (Classic topics) contains notions of hamiltonicity, planarity, connectivity, and subgraphs as well as the unsettled conjecture by Rosenfeldt and Barnette that the prism over a 3-connected planar graph is hamiltonian. Part III (Graphical invariants) presents different graph coloring invariants, largest independent set and the domination number with special emphasis on the famous conjecture of Vizing. Part IV (Metric aspects) contains properties of the Wiener index, the most explored topological index in mathematical chemistry, the property of the distance function to be additive on product graphs and culminates in the Graham-Winkler theorem, asserting that every connected graph has a unique canonical, isometric embedding into a Cartesian product. Part V (Algebraic and algorithmic issues) contains prime factorization of graphs and the description of their automorphism group, the distinguishing number, which measures the effort to break all symmetries in a graph and shows how the main result on the structure and the symmetries of Cartesian product lead to efficient factorization algorithms and the recognition of partial cubes.
Each chapter ends with a list of exercises, whose solutions are collected at the end of the book. This excellent textbook addresses a reader who wishes to apply graph theory at a higher or more special level. The prerequisites are previous exposure to fundamental notions of graph theory, discrete mathematics, and algebra. The list of refences includes 122 titles. The book also contains subject, name and symbol indices.

MSC:

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
05C90 Applications of graph theory
PDFBibTeX XMLCite