Scribd Logo
Upload

Welcome to Scribd!

  • 178 views

    Graph Theory: A First IN

    Uploaded by

    Hunny Verma
    This document is a table of contents for a textbook on graph theory. It introduces fundamental concepts in graph theory through 13 chapters, including topics like degrees of vertices, isomorphic graphs, trees, connectivity, traversability, matchings and factorizations, planarity, coloring graphs, Ramsey numbers, distance, and domination. Each chapter contains sections that define and explore different graph-theoretic concepts, and includes examples, theorems, and exercises. There are also three appendixes on sets and logic, equivalence relations and functions, and methods of proof in mathematics.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Graph Theory: A First IN

    Uploaded by

    Hunny Verma
    178 views4 pages
    This document is a table of contents for a textbook on graph theory. It introduces fundamental concepts in graph theory through 13 chapters, including topics like degrees of vertices, isomorphic graphs, trees, connectivity, traversability, matchings and factorizations, planarity, coloring graphs, Ramsey numbers, distance, and domination. Each chapter contains sections that define and explore different graph-theoretic concepts, and includes examples, theorems, and exercises. There are also three appendixes on sets and logic, equivalence relations and functions, and methods of proof in mathematics.

    Original Title

    66965924x

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document is a table of contents for a textbook on graph theory. It introduces fundamental concepts in graph theory through 13 chapters, including topics like degrees of vertices, isomorphic graphs, trees, connectivity, traversability, matchings and factorizations, planarity, coloring graphs, Ramsey numbers, distance, and domination. Each chapter contains sections that define and explore different graph-theoretic concepts, and includes examples, theorems, and exercises. There are also three appendixes on sets and logic, equivalence relations and functions, and methods of proof in mathematics.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    178 views4 pages

    Graph Theory: A First IN

    Uploaded by

    Hunny Verma
    This document is a table of contents for a textbook on graph theory. It introduces fundamental concepts in graph theory through 13 chapters, including topics like degrees of vertices, isomorphic graphs, trees, connectivity, traversability, matchings and factorizations, planarity, coloring graphs, Ramsey numbers, distance, and domination. Each chapter contains sections that define and explore different graph-theoretic concepts, and includes examples, theorems, and exercises. There are also three appendixes on sets and logic, equivalence relations and functions, and methods of proof in mathematics.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 4

    A FIRST COURSE IN

    GRAPH
    THEORY

    GARY CHART RAND


    and

    PING ZHANG
    Western Michigan University

    DOVER PUBLICATIONS, INC.


    Mineola, New York
    CONTENTS

    1. Introduction
    1.1. Graphs and Graph Models 1
    1.2. Connected Graphs 9
    1.3. Common Classes of Graphs 19
    1.4. Multigraphs and Digraphs 26

    2. Degrees
    2.1. The Degree of a Vertex 31
    2.2. Regular Graphs 38
    2.3. Degree Sequences 43
    2.4. Excursion: Graphs and Matrices 48
    2.5. Exploration: Irregular Graphs 50

    3. Isomorphic Graphs
    3.1. The Definition of Isomorphism 55
    3.2. Isomorphism as a Relation 63
    3.3. Excursion: Graphs and Groups 66
    3.4. Excursion: Reconstruction and Solvability 76

    4. Trees

    4.1. Bridges 85
    4.2. Trees 87
    4.3. The Minimum Spanning Tree Problem 94
    4.4. Excursion: The Number of Spanning Trees 100

    5. Connectivity
    5.1. Cut-Vertices 107
    5.2. Blocks 111
    5.3. Connectivity 115
    5.4. Menger's Theorem 124
    5.5. Exploration: Powers and Edge Labelings 130

    6. Traversability
    6.1. Eulerian Graphs 133
    6.2. Hamiltonian Graphs 140
    6.3. Exploration: Hamiltonian Walks 152
    6.4. Excursion: Early Books of Graph Theory 156
    viii

    7. Digraphs
    161
    7.1. Strong Digraphs
    7.2. Tournaments 169

    7.3. Excursion:Decision-Making 176

    7.4. Exploration: Wine Bottle Problems 180

    8. Matchings and Factorization

    8.1. Matchings 183


    8.2. Factorization 194
    8.3. Decompositions and Graceful Labelings 209
    8.4. Excursion: Instant Insanity 214
    8.5. Excursion: The Petersen Graph 220
    8.6. Exploration: Bi-Graceful Graphs 224

    9. Planar ity

    9.1. Planar Graphs 227


    241
    9.2. Embedding Graphs on Surfaces
    9.3. Excursion: Graph Minors 249

    9.4. Exploration: Embedding Graphs in Graphs 253

    10. Coloring Graphs


    10.1. The Four Color Problem 259
    10.2. Vertex Coloring 267
    10.3. Edge Coloring 281
    10.4. Excursion: The Heawood Map Coloring Theorem 289
    10.5. Exploration: Modular Coloring 294

    11. Ramsey Numbers


    11.1. The Ramsey Number of Graphs 297

    11.2. Turan's Theorem 307

    11.3. Exploration: Modified Ramsey Numbers 314

    11.4. Excursion: Erdos Numbers 321

    12. Distance
    12.1. The Center of a Graph 327
    12.2. Distant Vertices 333

    12.3. Excursion: Locating Numbers 341


    12.4. Excursion: Detour and Directed Distance 346
    12.5. Exploration: Channel Assignment 351
    12.6. Exploration: Distance Between Graphs 356
    ix

    13. Domination
    13.1. The Domination Number of a Graph 361
    13.2. Exploration: Stratification 372
    13.3. Exploration: Lights Out 377
    13.4. Excursion: And Still It Grows More Colorful 381

    Appendix 1. Sets and Logic 383

    Appendix 2. Equivalence Relations and Functions 388

    Appendix 3. Methods of Proof 392

    Solutions and Hints for Odd-Numbered Exercises 399

    References 427

    Index of Names 438


    Index of Mathematical Terms 441

    List of Symbols 448

    You might also like