This textbook covers a diversity of topics in graph and network theory, both from a theoretical standpoint, and from an applied modelling point of view. Mathematica® is used to demonstrate much of the modelling aspects. Graph theory and model building tools are developed in tandem with effective techniques for solving practical problems via computer implementation. The book is designed with three primary readerships in mind. Individual syllabi or suggested sequences for study are provided for each of three student audiences: mathematics, applied mathematics/operations research, and computer science. In addition to the visual appeal of each page, the text contains an abundance of gems. Most chapters open with real-life problem descriptions which serve as motivation for the theoretical development of the subject matter. Each chapter concludes with three different sets of exercises. The first set of exercises are standard and 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 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.

The material in this book has been organizedinto 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.

Offers a rich collection of exercises as direct applications of theory Visually appealing with more than 100 biographical and historical notes enhancing understanding and concepts Integrates theoretical and applied aspects of the material covered, some with real-life problems

Autorentext

Teresa W. Haynes has focused her research on domination in graphs for over 30 years and is perhaps best known for coauthoring the 1998 book Fundamentals of Domination in Graphs and the companion volume Domination in Graphs: Advanced Topics. She has also co-edited 2 volumes in Springer's Problem Books in Mathematics Graph Theory: Favorite Conjectures and Open Problems. Haynes is also a co-author of the Springer Briefs in Mathematics From Domination to Coloring: The Graph Theory of Stephen T. Hedetniemi. Upon receiving her PhD from the University of Central Florida in 1988, she joined East Tennessee State University, where she is currently professor in the Department of Mathematics and Statistics. Haynes has coauthored more than 200 papers on domination and domination-related concepts, which introduced some of the most studied concepts in domination, such as power domination, paired domination, double domination, alliances and broadcasts in graphs, and stratified domination. Stephen T. Hedetniemi is one of the earliest pioneers of domination in graphs along with E. J. Cockayne, who together proposed the theory of domination in graphs, in one of the most cited papers in the field in 1977. He received his PhD from the University of Michigan in 1966, with two world-class advisors, graph theorist Frank Harary, and the pioneer of genetic algorithms and MacArthur Fellowship winner, John Holland. He coauthored, the first book on domination in 1988 Fundamentals of Domination in Graphs, and co-edited a second book, Domination in Graphs: Advanced Topics. He also co-edited 2 volumes in Springer's Problem Books in Mathematics Graph Theory: Favorite Conjectures and Open Problems. Since 1974 he has coauthored more than 300 papers, 180 of which are on domination and domination-related concepts. Hedetniemi has introduced some of the most-studied concepts in domination theory, including total domination, independent domination, irredundance, Roman domination, power domination, alliances in graphs, signed and minus domination, fractional domination, domatic numbers, domination in grid graphs and chessboards, the first domination algorithms, the first domination NP-completeness results, and the first self-stabilizing domination algorithms. After leaving the University of Michigan, he taught computer science at the University of Iowa, and the University of Virginia, spent a visiting year at the University of Victoria with E. J. Cockayne, and then became department head of Computer and information Science at the University of Oregon. Since 1982 has been at Clemson University, where he served a five-year term as department head, and served on the Executive Committee of the Computing Accreditation Commission of ABET, Inc. He is currently Emeritus Professor of Computer Science in the School of Computing at Clemson University. Michael A. Henning has devoted much of his research interests to the field of domination theory in graphs. He has been both plenary and invited speakers at several international conferences and is a prolific researcher having published over 460 papers to date in international mathematics journals. Henning was born and schooled in South Africa having obtained his PhD at the University of Natal in April 1989. In January 1989, he started his academic career as a lecturer at the University of Zululand, before accepting a lectureship in mathematics at the former University of Natal in January 1991. In January 2000, he was appointed a full professor at the University of Natal, which later merged with the University of Durban-Westville to form the University of KwaZulu-Natal in January 2004. After spending almost 20years at the University of KwaZulu-Natal and one of its predecessors, the University of Natal, Michael moved to the U

Inhalt
Preface.- List of Algorithms.- List of Bibliographical Notes.- Part 1. Topics in network optimisation.- 1. An introduction to graphs.- 2. Graph connectedness.- 3. Algorithmic complexity.- 4. Optimal paths.- 5. Trees.- 6. Location problems.- 7. Maximum flow networks.- 8. Minimum-cost network flows.- Part 2. Topics in classical graph theory.- 9. Matchings.- 10. Eulerian graphs.- 11. Hamiltonian graphs.- 12. Graph connectivity.- 13. Planarity.- 14. Graph colouring.- 15. Oriented graphs. Part 3. Topics in modern graph theory.- 16. Domination in graphs.- 17. Ramsey Theory.- 18. Extremal graph theory.- 19. Graph enumeration.- 20. The probabilistic method.- Index.