Book:Gary Chartrand/Introductory Graph Theory

Gary Chartrand: Introductory Graph Theory

Published $\text {1985}$, Dover Publications, Inc.

ISBN 0-486-24775-9

Subject Matter

• Graph Theory

Republication with corrections of Graphs as Mathematical Models from $1977$.

Contents

Preface

Acknowledgements

Chapter l: Mathematical Models

1.1 Nonmathematical Models

1.2 Mathematical Models

1.3 Graphs

1.4 Graphs as Mathematical Models

1.5 Directed Graphs as Mathematical Models

1.6 Networks as Mathematical Models

Chapter 2: Elementary Concepts of Graph Theory

2.1 The Degree of a Vertex

2.2 Isomorphic Graphs

2.3 Connected Graphs

2.4 Cut-Vertices and Bridges

Chapter 3: Transportation Problems

3.1 The Königsberg Bridge Problem: An Introduction to Eulerian Graphs

3.2 The Salesman's Problem: An Introduction to Hamiltonian Graphs

Chapter 4: Connection Problems

4.1: The Minimal Cohnector Problem: An Introduction to Trees

4.2 Trees and Probability

4.3 PERT and the Critical Path Method

Chapter 5: Party Problems

5.1 The Problem of the Eccentric Hosts: An Introduction to Ramsey Numbers

5.2 The Dancing Problem: An Introduction to Matching

Chapter 6: Games and Puzzles

6.1 The Problem of the Four Multicolored Cubes: A Solution to "Instant Insanity"

6.2 The Knight's Tour

6.3 The Tower of Hanoi

6.4 The Three Cannibals and Three Missionaries Problem

Chapter 7: Digraphs and Mathematical Models

7.1 A Traffic System Problem: An Introduction to Orientable Graphs

7.2 Tournaments

7.3 Paired Comparisons and How to Fix Elections

Chapter 8: Graphs and Social Psychology

8.1 The Problem of Balance

8.2 The Problem of Clustering

8.3 Graphs and Transactional Analysis

Chapter 9

Planar Graphs and Coloring Problems

9.1 The Three Houses and Three Utilities Problem: An Introduction to Planar Graphs

9.2 A Scheduling Problem: An Introduction to Chromatic Numbers

9.3 The Four Color Problem

Chapter 10: Graphs and Other Mathematics

10.1 Graphs and Matrices

10.2 Graphs and Topology

10.3 Graphs and Groups

Appendix: Sets, Relations, Functions, Proofs

A.1 Sets and Subsets

A.2 Cartesian Products and Relations

A.3 Equivalence Relations

A.4 Functions

A.5 Theorems and Proofs

A.6 Mathematical Induction

Answers, Hints, and Solutions to Selected Exercises

Index

Next

Source work progress

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 4.2$: Trees and Probability -- there are gaps. Revisiting as follows:

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.2$: Isomorphic Graphs

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous): Appendix $\text{A}.6$: Mathematical Induction: Problem Set $\text{A}.6$: $41$ Complete except for final set of exercises (they go up to $55$) and some simple exercises on logic