Introductory Graph Theory (eBook)

Six Degrees of Paul Erdos Contrary to popular belief, mathematicians do quite often have fun. Take, for example, the phenomenon of the Erdos number. Paul Erdos (1913–1996), a prominent and productive Hungarian mathematician who traveled the world collaborating with other mathematicians on his research papers. Ultimately, Erdos published about 1,400 papers, by far the most published by any individual mathematician. About 1970, a group of Erdos's friends and collaborators created the concept of the "Erdos number" to define the "collaborative distance" between Erdos and other mathematicians. Erdos himself was assigned an Erdos number of 0. A mathematician who collaborated directly with Erdos himself on a paper (there are 511 such individuals) has an Erdos number of 1. A mathematician who collaborated with one of those 511 mathematicians would have an Erdos number of 2, and so on — there are several thousand mathematicians with a 2. From this humble beginning, the mathematical elaboration of the Erdos number quickly became more and more elaborate, involving mean Erdos numbers, finite Erdos numbers, and others. In all, it is believed that about 200,000 mathematicians have an assigned Erdos number now, and 90 percent of the world's active mathematicians have an Erdos number lower than 8. It's somewhat similar to the well-known Hollywood trivia game, Six Degrees of Kevin Bacon. In fact there are some crossovers: Actress-mathematician Danica McKellar, who appeared in TV's The Wonder Years, has an Erdos number of 4 and a Bacon number of 2. This is all leading up to the fact that Gary Chartrand, author of Dover's Introductory Graph Theory, has an Erdos number of 1 — and is one of many Dover authors who share this honor.

Chapter 1 Mathematical Models1.1 Nonmathematical Models1.2 Mathematical Models1.3 Graphs1.4 Graphs as Mathematical Models1.5 Directed Graphs as Mathematical Models1.6 Networks as Mathematical ModelsChapter 2 Elementary Concepts of Graph Theory2.1 The Degree of a Vertex2.2 Isomorphic Graphs2.3 Connected Graphs2.4 Cut-Vertices and BridgesChapter 3 Transportation Problems3.1 The Königsberg Bridge Problem: An Introduction to Eulerian Graphs3.2 The Salesman's Problem: An Introduction to Hamiltonian GraphsChapter 4 Connection Problems4.1 The Minimal Connector Problem: An Introduction to Trees*4.2 Trees and Probability4.3 PERT and the Critical Path MethodChapter 5 Party Problems5.1 The Problem of Eccentric Hosts: An Introduction to Ramsey Numbers5.2 The Dancing Problem: An Introduction to MatchingChapter 6 Games and Puzzles6.1 "The Problem of the Four Multicolored Cubes: A Solution to "Instant Insanity"6.2 The Knight's Tour6.3 The Tower of Hanoi6.4 The Three Cannibals and Three Missionaries ProblemChapter 7 Digraphs and Mathematical Models7.1 A Traffic System Problem: An Introduction to Orientable Graphs7.2 Tournaments7.3 Paired Comparisons and How to Fix ElectionsChapter 8 Graphs and Social Psychology8.1 The Problem of Balance8.2 The Problem of Clustering8.3 Graphs and Transactional AnalysisChapter 9 Planar Graphs and Coloring Problems9.1 The Three Houses and Three Utilities Problem: An Introduction to Planar Graphs9.2 A Scheduling Problem: An Introduction to Chromatic Numbers9.3 The Four Color Problem*Chapter 10 Graphs and Other Mathematics10.1 Graphs and Matrices10.2 Graphs and Topology10.3 Graphs and Groups"Appendix Sets, Relations, Functions, Proofs"A.1 Sets and SubsetsA.2 Cartesian Products and RelationsA.3 Equivalence RelationsA.4 FunctionsA.5 Theorems and ProofsA.6 Mathematical Induction"Answers, Hints, and Solutions to Selected Exercises"Index