Graphs and Networks. S. R. Kingan

Preface

      Network science is another name for the modern applications of graph theory and should be studied alongside the usual theorems and techniques in a graph theory course. On the other hand, data scientists, biologists, physicists, and social scientists using networks as models might be interested in the theory behind the results they use. This book attempts to bridge the growing division between graph theory and network science by weaving theory, algorithms, and applications together into the narrative. Only the theorems are numbered because it is through them that the subject unfolds. Moreover, a curated selection of theorems is presented to make the text read like a story, except that this is not fiction and the story never ends.

      Chapter 1 presents a broad overview of the book and the basic concepts and examples used throughout the book. Chapter 2 presents foundational topics such as trees, distance, and matrices that represent graphs. Chapters 3 and 4 contain applications found in network science books such as centrality measures, small‐world networks, and scale‐free networks. Their inclusion early in the book indicates their importance and emphasizes how little classical graph theory these applications require. They do, however, require a working knowledge of elementary linear algebra, probability, and statistics. The required concepts are in Appendices A and B. Chapter 5 and Appendices C and D provide an introduction to graph algorithms including graph traversal algorithms, greedy algorithms, and shortest path algorithms. Subsequently, algorithms are treated as an integral part of the story. Chapter 6 is a collection of results on Eulerian circuits, Hamiltonian cycles, coloring, and higher connectivity including Menger's Theorem and the Splitter Theorem. Chapter 7 provides an introduction to planar graphs. Chapter 8 is on flows, stable sets, matchings, and coverings, and ends with Edmonds' Blossom Algorithm, one of the finest examples of a graph algorithm.

The following two quotes by Jacob Lawrence and Albert Einstein, respectively, capture my approach to writing this book: “when the subject is strong, simplicity is the only way to treat it” and “everything should be made as simple as possible, but not simpler.” The book is full of results with short and simple proofs designed to build confidence in reading and understanding proofs. On the other hand, applications such as Google's PageRank require a fairly good grasp of linear algebra. Explaining PageRank without mentioning eigenvalues is certainly possible, however, doing so detracts from the ideas behind this application.

      This book is written so that students can review the material and come prepared for a discussion in the classroom. The selection of results in this book gradually increases in difficulty and makes self–study possible. The exercises encourage playing with examples and experimentation. Each chapter has a list of topics suitable for independent study projects and research experiences.

      The book also serves as a guide for navigating the large amount of free graph theory and network science resources on the web. Most papers can be obtained within seconds via a web search. Many older textbooks are freely available on the Internet. All these excellent resources for further study are built into the narrative. Students are encouraged to begin gathering original sources as a matter of routine. A seemingly random collection of papers may initially have no connection, but gradually patterns will appear and point toward a research project.

      My husband Robert Kingan helped me with the algorithms, figures and references. This book would never have been completed without his encouragement and assistance. My sons Rohan, Arun, and Ravi cheered me on. My colleagues from the New York combinatorics group Kira Adaricheva, Deepak Bal, Nadia Benakli, Jonathan Cutler, Ezra Halleck, Joseph Malkevitch, Eric Rowland, Kerry Ojakian, Peter Winkler, and Mingxian Zhong gave valuable feedback. Many thanks to Noemi Halpern and Murray Hochberg for their long standing support and encouragement and the anonymous reviewers for their nice reviews of my original book proposal. My students helped me by finding typos and errors. I was able to refine explanations by teaching the same topics over and over again. Last, but not least, Susanne Filler, the original acquisitions editor for this book, the expert team at Wiley, Inc. Kimberly Hill, Kalli Schultea, and Gayathree Sekar have been patient and easy to work with. I am grateful to all noted here and to many others who helped in bringing this book to fruition.

My goal in writing this book will be accomplished if students find the material interesting; perhaps interesting enough to pursue research in it. I wrote the book so that chapters can be added ad infinitum. Is your favorite topic missing? Let me know and I'll write a chapter on it and post it online. This is a living and growing book. The book that you hold in your hands is the beginning of a never–ending story.

       S. R. Kingan

      Brooklyn College and The Graduate Center

      The City University of New York

      New York, NY