Handbook of Graph Theory, Second Edition: 2nd Edition (Hardback) book cover

Handbook of Graph Theory, Second Edition

Edited by Jonathan L. Gross, Jay Yellen, Ping Zhang

© 2013 – Chapman and Hall/CRC

1,630 pages | 435 B/W Illus.

Purchasing Options:
Paperback: 9781138199668
pub: 2016-09-30
Available for pre-order
Save $12.00
Hardback: 9781439880180
pub: 2013-12-17
Save $29.19

About the Book

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.


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

Table of Contents

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.

About the Editors

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.

About the Series

Discrete Mathematics and Its Applications

Learn more…

Subject Categories

BISAC Subject Codes/Headings:
COMPUTERS / Operating Systems / General
COMPUTERS / Programming / Algorithms
MATHEMATICS / Arithmetic
MATHEMATICS / Combinatorics