Fundamentals of Graph Theory

Contents: Preface. 1. Graph theory basics. 2. Algebraic graph theory. 3. Directed acyclic graphs. 4. k-edge-connected graph. 5. Route problems. 6. Bipartite graph. 7. Chromatic polynomial. 8. Ramsey theory. Bibliography. Index. Graph theory has become a primary tool for detecting numerous hidden structures in various information networks including the internet social networks, and biological network. It is a mathematical model of any system that involves a binary relation. The theory is intimately related to many branches of mathematics including group theory, matrix theory, probability, topology, and combinatorics. The intuitive appeal of graphs arises from their diagrammatic representation. They are widely used in physics, chemistry, computer science, electrical engineering, civil engineering, architecture, genetics, psychology, sociology, economics, linguistics, and operations research. One of the usages of graph theory is to give a unified formalism for many very different looking problems. It then suffices to present algorithms in this common formalism. This has lead to the birth of a special class of algorithms the so called graph algorithms.