Author | Balakrishnan, R. author |
---|---|
Title | A Textbook of Graph Theory [electronic resource] / by R. Balakrishnan, K. Ranganathan |
Imprint | New York, NY : Springer New York : Imprint: Springer, 2000 |
Connect to | http://dx.doi.org/10.1007/978-1-4419-8505-7 |
Descript | XI, 228 p. online resource |
I Basic Results -- 1.0 Introduction -- 1.1 Basic Concepts -- 1.2 Subgraphs -- 1.3 Degrees of Vertices -- 1.4 Paths and Connectedness -- 1.5 Automorphism of a Simple Graph -- 1.6 Line Graphs -- 1.7 Operations on Graphs -- 1.8 An Application to Chemistry -- 1.9 Miscellaneous Exercises -- Notes -- II Directed Graphs -- 2.0 Introduction -- 2.1 Basic Concepts -- 2.2 Tournaments -- 2.3 K-Partite Tournaments -- Notes -- III Connectivity -- 3.0 Introduction -- 3.1 Vertex Cuts and Edge Cuts -- 3.2 Connectivity and Edge-Connectivity -- 3.3 Blocks -- 3.4 Edge-Connectivity of a Graph -- 3.5 Mengerโs Theorem -- 3.6 Exercises -- Notes -- IV Trees -- 4.0 Introduction -- 4.1 Definition, Characterization, and Simple Properties -- 4.2 Centers and Centroids -- 4.3 Counting the Number of Spanning Trees -- 4.4 4.4 Cayleyโs Formula -- 4.5 Helly Property -- 4.6 Exercises -- Notes -- V Independent Sets and Matchings -- 5.0 Introduction -- 5.1 Vertex Independent Sets and Vertex Coverings -- 5.2 Edge-Independent Sets -- 5.3 Matchings and Factors -- 5.4 Matchings in Bipartite Graphs -- 5.5 * Perfect Matchings and the Tutte Matrix -- Notes -- VI Eulerian and Hamiltonian Graphs -- 6.0 Introduction -- 6.1 Eulerian Graphs -- 6.2 Hamiltonian Graphs -- 6.3 * Pancyclic Graphs -- 6.4 Hamilton Cycles in Line Graphs -- 6.5 2-Factorable Graphs -- 6.6 Exercises -- Notes -- VII Graph Colorings -- 7.0 Introduction -- 7.1 Vertex Colorings -- 7.2 Critical Graphs -- 7.3 Triangle-Free Graphs -- 7.4 Edge Colorings of Graphs -- 7.5 Snarks -- 7.6 Kirkmanโs Schoolgirls Problem -- 7.7 Chromatic Polynomials -- Notes -- VIII Planarity -- 8.0 Introduction -- 8.1 Planar and Nonplanar Graphs -- 8.2 Euler Formula and Its Consequences -- 8.3 K5 and K3,3 are Nonplanar Graphs -- 8.4 Dual of a Plane Graph -- 8.5 The Four-Color Theorem and the Heawood Five-Color Theorem -- 8.6 Kuratowskiโs Theorem -- 8.7 Hamiltonian Plane Graphs -- 8.8 Tait Coloring -- Notes -- IX Triangulated Graphs -- 9.0 Introduction -- 9.1 Perfect Graphs -- 9.2 Triangulated Graphs -- 9.3 Interval Graphs -- 9.4 Bipartite Graph B(G)of a Graph G -- 9.5 Circular Arc Graphs -- 9.6 Exercises -- 9.7 Phasing of Traffic Lights at a Road Junction -- Notes -- X Applications -- 10.0 Introduction -- 10.1 The Connector Problem -- 10.2 Kruskalโs Algorithm -- 10.3 Primโs Algorithm -- 10.4 Shortest-Path Problems -- 10.5 Timetable Problem -- 10.6 Application to Social Psychology -- 10.7 Exercises -- Notes -- List of Symbols -- References