Topics in Graph Theory: Graphs and Their Cartesian Product 1st Edition by Wilfried Imrich (PDF)

Description

From specialists in the field, you will learn about interesting connections and recent developments in the field of graph theory by looking in particular at Cartesian products-arguably the most important of the four standard graph products. Many new results in this area appear for the first time in print in this book. Written in an accessible way, this book can be used for personal study in advanced applications of graph theory or for an advanced graph theory course.

User’s Reviews

Reviews from Amazon users which were colected at the time this book was published on the website:

⭐In the book

⭐by Wilfried Imrich and Sandi Klavzar, published in the World Mathematical Year 2000, the main results on the structure and algorithmic properties of the four principal graph products (Cartesian, direct, strong, and lexicographic) were brought together for the first time. Now the authors have joined forces with Douglas F. Rall in a new book. All three authors being among the leading researchers in the area of graph products, it is not surprising that the new book contains many state-of-the-art results which appeared in scientific journals at about the same time as this book was published. Even before its release the book was thoroughly tested in several graduate-level courses at the authors’ home universities.The thread of the book are Cartesian products of graphs and their subgraphs, which – due to their nice metric properties – have numerous applications in coding theory, radio-frequency assignment, theoretical chemistry, etc. Following this thread, the reader encounters all the principal areas of graph theory: from connectivity, hamiltonicity and planarity, through different invariants, to the metric, algebraic and algorithmic aspects of graphs. The book is divided into five main parts and 18 chapters. The average length of a chapter is below ten pages which makes the book accessible also to the less experienced reader. Another praiseworthy feature are the “trailers” at the start of each chapter which give a short preview of the chapter and place it in the broader context.In part I we learn the definition and the basic properties of the Cartesian product of graphs. We also meet some important families of graphs which are either defined or characterised in terms of the Cartesian product, such as the hypercubes (= Cartesian powers of the complete graph K2), Hamming graphs (= Cartesian products of arbitrary complete graphs), and Hanoi graphs (= spanning subgraphs of Hamming graphs, describing the state space in the well-known Tower of Hanoi problem).Part II discusses hamiltonicity, planarity, crossing numbers, connectivity, and subgraphs, first in general, then in Cartesian-product graphs. The still-open 1973 conjecture of Rosenfeld and Barnette that a prism (= Cartesian product with K2) over any 3-connected planar graph is hamiltonian is stated, and an elegant proof of the theorem that the k-tuple prism (= Cartesian product with K2^k) over such a graph is hamiltonian for all k >= 2 is given.Part III investigates graph invariants such as independence number, chromatic number, P-chromatic number (where P is some hereditary property of graphs), circular chromatic number, list chromatic number, L(2,1)-labeling number, chromatic index, and domination number. The authors study the question of what can be said about the value of a certain invariant of a Cartesian product provided that one knows its values on the factors. As we learn, the answers can differ widely for different invariants. For example, while it is relatively easy to seethat the chromatic number of a Cartesian product equals the largest chromatic number of its factors, the 1968 Vizing conjecture stating that the domination number of a Cartesian product equals or exceeds the product of domination numbers of its factors is still open.As already mentioned, the widespread applicability of Cartesian-product graphs stems primarily from their nice metric properties; these are the subject of Part IV of the book. Here the authors show that the diameter resp. the radius of a Cartesian-product graph equals the sum of the diameters resp. the radii of its factors, and that its Wiener index (a number used in theoretical chemistry to describe certain physico-chemical properties of molecules) can be easily computed from the corresponding indices of its factors. Among the subgraphs of a Cartesian-product graph G, special attention is devoted to the isometric subgraphs whose metric agrees with that of G restricted to the vertex set of the subgraph. So, for instance, partial cubes are the isometric subgraphs of hypercubes, and partial Hamming graphs are the isometric subgraphs of Hamming graphs. This part of the book ends with a proof of the Fundamental Theorem of the metric theory of Cartesian-product graphs which says: Every graph has a canonical metric representation, i.e., a unique isometric embedding into a Cartesian-product graph with maximum number of irredundant factors.Part V of the book surveys algebraic and algorithmic aspects of Cartesian-product graphs. The set of all graphs (with isomorphic graphs identified), equipped with the operation of Cartesian product, is an abelian monoid. In analogy to prime numbers, those graphs which do not possess a non-trivial Cartesian-product factorization are called prime graphs. The authors show that unique factorization into prime graphs holds for all connected graphs, while disconnected graphs may have several distinct such factorizations. Therefore it is quite surprising that the cancellation property, as well as uniqueness of r-th roots, hold for all graphs. Using uniqueness of factorization into prime graphs, the authors determine the structure of the automorphism group of a connected Cartesian-product graph: it is isomorphic to the group of automorphisms of the disjoint union of the prime factors of the graph. Then they use these results to analyze the distinguishing number of a graph, i.e., the least natural number d such that there is a labeling of the vertices with d labels, preserved only by the identity automorphism. In this way they prove that the distinguishing number of the k-th Cartesian power of any non-trivial connected graph, different from K2 and K3, equals 2 for all k >= 2. In the last chapter of the book, the authors present two important algorithms: for factoring a connected graph into prime graphs, and for recognition of partial cubes, both with time complexity O(m n) (where n is the number of vertices and m the number of edges of the given graph).An especially valuable part of the book are the more than 200 exercises which conclude every chapter. For each of the exercises either a full solution or at least a hint is provided at the end of the book. The list of 122 references is followed by the name, symbol, and subject indices.Researchers in graph theory will find in this book an encyclopedia of known results on graph products, and teachers will welcome it as an excellent textbook. It will also be enjoyed by all other devotees of graph theory who wish to learn the state of the art in this area.

Keywords

Free Download Topics in Graph Theory: Graphs and Their Cartesian Product 1st Edition in PDF format
Topics in Graph Theory: Graphs and Their Cartesian Product 1st Edition PDF Free Download
Download Topics in Graph Theory: Graphs and Their Cartesian Product 1st Edition 2008 PDF Free
Topics in Graph Theory: Graphs and Their Cartesian Product 1st Edition 2008 PDF Free Download
Download Topics in Graph Theory: Graphs and Their Cartesian Product 1st Edition PDF
Free Download Ebook Topics in Graph Theory: Graphs and Their Cartesian Product 1st Edition