Graphs & Digraphs, Fourth Edition

Published:
October 28, 2004 by Chapman and Hall/CRC - 386 Pages
Author(s):
Gary Chartrand, Western Michigan University, Kalamazoo, USA; Linda Lesniak, Drew University, Madison, New Jersey, USA; Ping Zhang, Western Michigan University, Kalamazoo, USA
Request
Evaluation Copy

Purchasing Options

Hardback
Not available
in your region
ISBN 9781584883906
Cat# C3901
 

Features

  • Presents a complete introduction to graph theory
  • Provides detailed coverage of emerging and rapidly growing areas of graph theory, such as domination, distance, Ramsey theory, and list colorings
  • Includes in each chapter exercises that reinforce the definitions and concepts and build valuable insightA manual containing suggested solution to many of the exercises is available to instructors with qualifying course adoptions.

    • Summary

    With a growing range of applications in fields from computer science to chemistry and communications networks, graph theory has enjoyed a rapid increase of interest and widespread recognition as an important area of mathematics. Through more than 20 years of publication, Graphs & Digraphs has remained a popular point of entry to the field, and through its various editions, has evolved with the field from a purely mathematical treatment to one that also addresses the mathematical needs of computer scientists.

    Carefully updated, streamlined, and enhanced with new features, Graphs & Digraphs, Fourth Edition reflects many of the developments in graph theory that have emerged in recent years. The authors have added discussions on topics of increasing interest, deleted outdated material, and judiciously augmented the Exercises sections to cover a range of problems that reach beyond the construction of proofs.

    New in the Fourth Edition:

  • Expanded treatment of Ramsey theory
  • Major revisions to the material on domination and distance
  • New material on list colorings that includes interesting recent results
  • A solutions manual covering many of the exercises available to instructors with qualifying course adoptions
  • A comprehensive bibliography including an updated list of graph theory books

    Every edition of Graphs & Digraphs has been unique in its reflection the subject as one that is important, intriguing, and most of all beautiful. The fourth edition continues that tradition, offering a comprehensive, tightly integrated, and up-to-date introduction that imparts an appreciation as well as a solid understanding of the material.

    • Table of Contents

    INTRODUCTION TO GRAPHS AND DIGRAPHS
    Graphs
    Degree Sequences
    Connected Graphs and Distance
    Digraphs and Multigraphs
    THE STRUCTURE OF GRAPHS
    Cut-Vertices, Bridges and Blocks
    The Automorphism Group of a Graph
    Cayley Color Graphs
    The Reconstruction Problem
    TREES AND CONNECTIVITY
    Elementary Properties of Trees
    Arboricity and Vertex-Arboricity
    Connectivity and Edge-Connectivity
    Menger's Theorem
    The Toughness of a Graph
    EULERIAN AND HAMILTONIAN GRAPHS AND DIGRAPHS
    Eulerian Graphs and Digraphs
    Hamiltonian Graphs and Digraphs
    Line Graphs and Powers of Graphs
    DIRECTED GRAPHS
    Strong Digraphs
    Tournaments
    Hamiltonian Tournaments
    PLANAR GRAPHS
    The Euler Identity
    Characterizations of Planar Graphs
    Hamiltonian Planar Graphs
    Crossing Number and Thickness
    GRAPH EMBEDDINGS
    The Genus of a Graph
    2-Cell Embeddings of Graphs
    The Maximum Genus of a Graph
    GRAPH COLORINGS
    Vertex Colorings
    Edge Colorings
    Map Colorings and Flows
    MATCHINGS, FACTORS AND DECOMPOSITIONS
    Matchings and Independence in Graphs
    Factorizations and Decompositions
    Labelings of Graphs
    DOMINATION IN GRAPHS
    The Domination Number of a Graph
    The Independent Domination Number of a Graph
    Other Domination Parameters
    EXTREMAL GRAPH THEORY
    Tura´n's Theorem
    Extremal Results on Graphs
    Cages
    RAMSEY THEORY
    Classical Ramsey Numbers
    Generalized Ramsey Theory
    Rainbow Ramsey Numbers
    THE PROBABILISTIC METHOD IN GRAPH THEORY
    The Probabilistic Method
    Random Graphs

    Glossary of Symbols
    Graph Theory Books
    References

    Editorial Reviews

    "a popular point of entry to the field…has evolved with the field from a purely mathematical treatment to one that also addresses the needs of computer scientists."
    -L'Enseignement Mathématique

    "…emphasizes clear exposition, well-written proofs, and many original and innovative exercises-of varying difficulty and challenge…For 25 years, Graphs & Digraphs, in its various editions, has served as an exemplary introduction to the emerging mathematical disciplines of graph theories, for advanced undergraduate and graduate students. It has also served established graph theorists, combinatorialists, and other discrete mathematicians, as well as computer scientists and chemists, as a useful reference work. The fourth edition continues these fine traditions."
    -Zentralblatt MATH

    Related Titles