Handbook of Graph Theory

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 GraphsFundamentals of Graph Theory, Jonathan L. Gross and Jay YellenFamilies of Graphs and Digraphs, Lowell W. BeinekeHistory of Graph Theory, Robin J. Wilson Graph RepresentationComputer Representation of Graphs, Alfred V. AhoGraph Isomorphism, Brendan D. McKayThe Reconstruction Problem, Josef LauriRecursively Constructed Graphs, Richard B. Borie, R. Gary Parker, and Craig A. ToveyStructural Graph Theory, Maria Chudnovsky Directed GraphsBasic Digraph Models and Properties, Jay YellenDirected Acyclic Graphs, Stephen B. MaurerTournaments, K.B. Reid Connectivity and TraversabilityConnectivity Properties and Structure, Camino Balbuena, Josep Fàbrega, and Miguel Angel FiolEulerian Graphs, Herbert FleischnerChinese Postman Problems, R. Gary Parker and Richard B. BorieDeBruijn Graphs and Sequences, A.K. DewdneyHamiltonian Graphs, Ronald J. GouldTraveling Salesman Problems, Gregory GutinFurther Topics in Connectivity, Josep Fàbrega and Miguel Angel Fiol Colorings and Related TopicsGraph Coloring, Zsolt TuzaFurther Topics in Graph Coloring, Zsolt TuzaIndependence and Cliques, Gregory GutinFactors and Factorization, Michael PlummerApplications to Timetabling, Edmund Burke, Dominique de Werra, and Jeffrey KingstonGraceful Labelings, Joseph A. Gallian Algebraic Graph TheoryAutomorphisms, Mark E. WatkinsCayley Graphs, Brian AlspachEnumeration, Paul K. StockmeyerGraphs and Vector Spaces, Krishnaiyan "KT" ThulasiramanSpectral Graph Theory, Michael DoobMatroidal Methods in Graph Theory, James Oxley Topological Graph TheoryGraphs on Surfaces, Tomaz Pisanski and Primoz PotocnikMinimum Genus and Maximum Genus, Jianer ChenGenus Distributions, Jonathan L. GrossVoltage Graphs, Jonathan L. GrossThe Genus of a Group, Thomas W. TuckerMaps, Roman Nedela and Martin SkovieraRepresentativity, Dan ArchdeaconTriangulations, Seiya NegamiGraphs and Finite Geometries, Arthur T. WhiteCrossing Numbers, R. Bruce Richter and Gelasio Salazar Analytic Graph TheoryExtremal Graph Theory, Bela Bollobas and Vladimir NikiforovRandom Graphs, Nicholas WormaldRamsey Graph Theory, Ralph J. FaudreeThe Probabilistic Method, Alan Frieze and Po-Shen LohGraph Limits, Bojan Mohar Graphical MeasurementDistance in Graphs, Gary Chartrand and Ping ZhangDomination in Graphs, Teresa W. Haynes and Michael A. HenningTolerance Graphs, Martin Charles GolumbicBandwidth, Robert C. BrighamPursuit-Evasion Problems, Richard B. Borie, Sven Koenig, and Craig A. Tovey Graphs in Computer ScienceSearching, Harold N. GabowDynamic Graph Algorithms, Camil Demetrescu, Irene Finocchi, and Giuseppe F. ItalianoDrawings of Graphs, Emilio Di Giacomo, Giuseppe Liotta, and Roberto TamassiaAlgorithms on Recursively Constructed Graphs, Richard B. Borie, R. Gary Parker, and Craig A. ToveyFuzzy Graphs, John N. Mordeson and D.S. MalikExpander Graphs, Mike Krebs and Anthony ShaheenVisibility Graphs, Alice M. Dean and Joan P. Hutchinson Networks and FlowsMaximum Flows, Clifford SteinMinimum Cost Flows, Lisa FleischerMatchings and Assignments, Jay Sethuraman and Douglas R. Shier Communication NetworksComplex Networks, Anthony Bonato and Fan ChungBroadcasting and Gossiping, Hovhannes A. Harutyunyan, Arthur L. Liestman, Joseph G. Peters, and Dana RichardsCommunication Network Design Models, Prakash Mirchandani and David Simchi-LeviNetwork Science for Graph Theorists, David C. Arney and Steven B. Horton Natural Science and Processes Chemical Graph Theory, Ernesto Estrada and Danail BonchevTies between Graph Theory and Biology, Jacek Blazewicz, Marta Kasprzak, and Nikos Vlassis Index 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.