Graph and Network Theory

This textbook covers a wide variety of topics in graph and network theory, both from a theoreticalstandpoint and from an applied modelling point of view (while demonstrating the use of Mathematica in the modelling aspect). Graph theory is developed as a mathematical subject in its own right and useful model building tools are developed in tandem with effective solution techniques to solving practical problems via computer implementation. Most chapters open with real-life problem descriptions which serve as motivation for the theoreticaldevelopment of subject matter. Each chapter concludes with three different sets of exercises. The first set of exercises contains standard exercises geared toward the more mathematically inclined reader. Many of these are routine exercises, designed to test understanding of the material in the text, but some are more challenging. The second set of exercises is earmarked for the computer technologically savvy reader and offer computer exercises using Mathematica. The final set of exercises consists of larger projects aimed at equipping those readers with backgrounds in the applied sciences to apply the necessary skills learned in the chapter in the context of real-world problem solving. Additionally, each chapter offers biographical notes as well as pictures of graph theorists and mathematicians who have contributed significantly to the development of the results documented in the chapter. These notes are meant to bring the topics covered to life, allowing the reader to associate faces with some of the important discoveries and results presented. In total, approximately 100 biographical notes are presented throughout the book.  Individual syllabi or suggested sequences for study are provided for each of 3 student audiences: Mathematics, applied mathematics/operations research, and computer science. The material in this book has been organized into three distinct parts, each with a different focus. The first part is devoted to topics in network optimization, with a focus on basic notions in algorithmic complexity and the computation of optimal paths, shortest spanning trees, maximum flows and minimum-cost flows in networks, as well as the solution of network location problems. The second part is devoted to a variety of classical problems in graph theory, including problems related to matchings, edge and vertex traversal, connectivity, planarity, edge and vertex coloring, and orientations of graphs. Finally, the focus in the third part is on modern areas of study in graph theory, covering graph domination, Ramsey theory, extremal graph theory, graph enumeration, and application of the probabilistic method.