1632 Pages 435 B/W Illustrations
    by Chapman & Hall

    In the ten years since the publication of the best-selling first edition, more than 1,000 graph theory papers have been published each year. Reflecting these advances, Handbook of Graph Theory, Second Edition provides comprehensive coverage of the main topics in pure and applied graph theory. This second edition—over 400 pages longer than its predecessor—incorporates 14 new sections.

    Each chapter includes lists of essential definitions and facts, accompanied by examples, tables, remarks, and, in some cases, conjectures and open problems. A bibliography at the end of each chapter provides an extensive guide to the research literature and pointers to monographs. In addition, a glossary is included in each chapter as well as at the end of each section. This edition also contains notes regarding terminology and notation.

    With 34 new contributors, this handbook is the most comprehensive single-source guide to graph theory. It emphasizes quick accessibility to topics for non-experts and enables easy cross-referencing among chapters.

    Introduction to Graphs
    Fundamentals of Graph Theory, Jonathan L. Gross and Jay Yellen
    Families of Graphs and Digraphs, Lowell W. Beineke
    History of Graph Theory, Robin J. Wilson

    Graph Representation
    Computer Representation of Graphs, Alfred V. Aho
    Graph Isomorphism, Brendan D. McKay
    The Reconstruction Problem, Josef Lauri
    Recursively Constructed Graphs, Richard B. Borie, R. Gary Parker, and Craig A. Tovey
    Structural Graph Theory, Maria Chudnovsky

    Directed Graphs
    Basic Digraph Models and Properties, Jay Yellen
    Directed Acyclic Graphs, Stephen B. Maurer
    Tournaments, K.B. Reid

    Connectivity and Traversability
    Connectivity Properties and Structure, Camino Balbuena, Josep Fàbrega, and Miguel Angel Fiol
    Eulerian Graphs, Herbert Fleischner
    Chinese Postman Problems, R. Gary Parker and Richard B. Borie
    DeBruijn Graphs and Sequences, A.K. Dewdney
    Hamiltonian Graphs, Ronald J. Gould
    Traveling Salesman Problems, Gregory Gutin
    Further Topics in Connectivity, Josep Fàbrega and Miguel Angel Fiol

    Colorings and Related Topics
    Graph Coloring, Zsolt Tuza
    Further Topics in Graph Coloring, Zsolt Tuza
    Independence and Cliques, Gregory Gutin
    Factors and Factorization, Michael Plummer
    Applications to Timetabling, Edmund Burke, Dominique de Werra, and Jeffrey Kingston
    Graceful Labelings, Joseph A. Gallian

    Algebraic Graph Theory
    Automorphisms, Mark E. Watkins
    Cayley Graphs, Brian Alspach
    Enumeration, Paul K. Stockmeyer
    Graphs and Vector Spaces, Krishnaiyan "KT" Thulasiraman
    Spectral Graph Theory, Michael Doob
    Matroidal Methods in Graph Theory, James Oxley

    Topological Graph Theory
    Graphs on Surfaces, Tomaz Pisanski and Primoz Potocnik
    Minimum Genus and Maximum Genus, Jianer Chen
    Genus Distributions, Jonathan L. Gross
    Voltage Graphs, Jonathan L. Gross
    The Genus of a Group, Thomas W. Tucker
    Maps, Roman Nedela and Martin Skoviera
    Representativity, Dan Archdeacon
    Triangulations, Seiya Negami
    Graphs and Finite Geometries, Arthur T. White
    Crossing Numbers, R. Bruce Richter and Gelasio Salazar

    Analytic Graph Theory
    Extremal Graph Theory, Bela Bollobas and Vladimir Nikiforov
    Random Graphs, Nicholas Wormald
    Ramsey Graph Theory, Ralph J. Faudree
    The Probabilistic Method, Alan Frieze and Po-Shen Loh
    Graph Limits, Bojan Mohar

    Graphical Measurement
    Distance in Graphs, Gary Chartrand and Ping Zhang
    Domination in Graphs, Teresa W. Haynes and Michael A. Henning
    Tolerance Graphs, Martin Charles Golumbic
    Bandwidth, Robert C. Brigham
    Pursuit-Evasion Problems, Richard B. Borie, Sven Koenig, and Craig A. Tovey

    Graphs in Computer Science
    Searching, Harold N. Gabow
    Dynamic Graph Algorithms, Camil Demetrescu, Irene Finocchi, and Giuseppe F. Italiano
    Drawings of Graphs, Emilio Di Giacomo, Giuseppe Liotta, and Roberto Tamassia
    Algorithms on Recursively Constructed Graphs, Richard B. Borie, R. Gary Parker, and Craig A. Tovey
    Fuzzy Graphs, John N. Mordeson and D.S. Malik
    Expander Graphs, Mike Krebs and Anthony Shaheen
    Visibility Graphs, Alice M. Dean and Joan P. Hutchinson

    Networks and Flows
    Maximum Flows, Clifford Stein
    Minimum Cost Flows, Lisa Fleischer
    Matchings and Assignments, Jay Sethuraman and Douglas R. Shier

    Communication Networks
    Complex Networks, Anthony Bonato and Fan Chung
    Broadcasting and Gossiping, Hovhannes A. Harutyunyan, Arthur L. Liestman, Joseph G. Peters, and Dana Richards
    Communication Network Design Models, Prakash Mirchandani and David Simchi-Levi
    Network Science for Graph Theorists, David C. Arney and Steven B. Horton

    Natural Science and Processes
    Chemical Graph Theory, Ernesto Estrada and Danail Bonchev
    Ties between Graph Theory and Biology, Jacek Blazewicz, Marta Kasprzak, and Nikos Vlassis


    A Glossary appears at the end of each chapter.


    Jonathan Gross is a professor of computer science at Columbia University. A recipient of numerous awards and research grants, Dr. Gross is the coauthor of several books and the inventor of the voltage graph, a construct widely used in topological graph theory and other areas. His current research interests include the genus distribution of graphs, computer graphics, and knot theory.

    Jay Yellen is the Archibald Granville Bush Professor of Mathematics at Rollins College, where he has received several teaching and research awards. Dr. Yellen has coauthored one book with Dr. Gross, written materials for IBM courses, and conducted workshops for secondary-school mathematics teachers. His current research interests include graph theory, discrete optimization, and graph algorithms for software testing and course timetabling.

    Ping Zhang is a professor of mathematics at Western Michigan University. Dr. Zhang has coauthored five books. Her research interests include algebraic combinatorics and colorings, distance and convexity, traversability, decompositions, and domination within graph theory.

    Praise for the First Edition:
    … a fine guide to various literatures, especially for topics like Ramsey theory … . Many first-rate mathematicians have contributed, making the exposition's quality high overall. …. Highly recommended.
    CHOICE, January 2005, Vol. 42, No. 05