Topics in Graph Theory. Graphs and Their Cartesian Product
This book is focused on the Cartesian product of graphs. This graph operation stems from algebraic and categorical concepts and the prime and simplest example is the hypercube - the Cartesian power of a single edge. With the wealth of well-known results on hypercubes (including error-correcting codes in the Hamming metrics), it is worthwhile to explore the realm of products of graphs. Many classical topics are discussed with respect to the Cartesian product. The first section gives basics about the Cartesian product. The next two sections deal with graph properties like independence, chromatic numbers and crossing numbers. The fourth section discusses distance in the Cartesian product and the last section shows some connections with algebra and algorithms. Reading the book requires only a basic knowledge of graphs. The book is suitable for advanced undergraduates or beginning graduate students interested in graph theory. Every chapter is concluded with many exercises. Hints and solutions to the exercises are provided at the end of the book. The manuscript of the book was used during courses at the University of Maribor, the Mountanuniversität Loeben and Furman University. The book could be used as a textbook for an advanced graph theory course.