Theory of Graphs (Dover Publications Inc.)

Introduction1 General Definitions Sets and Multivalued Functions Paths and Circuits of a Graph Chains and Cycles of a Graph2 Descendance Relations Weak Ordering Associated with a Graph Inductive Graphs and Bases3 The Ordinal Function and the Grundy Function on an Infinite Graph General Remarks Concerning Infinite Graphs Ordinal Function Grundy Functions Operations over Graphs4 The Fundamental Numbers of the Theory of Graphs Cyclomatic Number Chromatic Number Methods for Finding the Chromatic Number Coefficient of Internal Stability Coefficient of External Stability5 Kernels of a Graph Existence and Uniqueness Theorems Application to Grundy Functions6 Games on a Graph Nim Type Games The General Definition of a Game (with Perfect Information) Strategies7 The Problem of the Shortest Route Stepwise Procedures Various Generalizations8 Transport Networks The Problem of Maximum Flow The Problem of Minimum Flow Problems of Flow when a Set of Values is Associated with each Arc Infinite Transport Networks9 The Theorem of the Demi-Degrees Inward or Outward Demi-Degree10 Matching of a Simple Graph The Maximum Matching Problem Deficiency of a Simple Graph The Hungarian Method Extensions to the Infinite Case Application to the Theory of Matrices11 Factors Hamiltonian Paths and Circuits Factors and Methods for Determining Them The Problem of Finding a Partial Graph with Given Demi-Degrees12 Centres of a Graph Centrees Radius13 The Diameter of a Strongly Connected Graph General Remarks on Strongly Connected Graphs without Loops Diameter14 The Matrix Associated with a Graph The Use of standard Matrix Operations Problems of Enumeration The Problem of the Leader The Use of Boolean Operations15 Incidence Matrices Matrices with the Unimodular Property Systems with the Unimodular Property Cyclomatic Matrices16 Trees and Arborescences Trees Analytic Treatment Arborescences17 Euler's Problem Eulerian Cycles Eulerian Circuits18 Matching in the General Case The Theory of Alternating Chains The Determination of a Partial Graph with Given Degrees Perfect Matching Application to the Coefficient of Internal Stability19 Semi-Factors Hamiltonian Cycles and Semi-Factors A Necessary and Sufficient Condition for the Existence of a Semi-Factor20 The Connectivity of a Graph Articulation Points Biconnected Graphs h-Connected Graphs21 Planar Graphs General Properties GeneralizationAppendix 1 Note on the General Theory of GamesAppendix 2 Note on Transport ProblemsBibliographyList of SymbolsIndex of Terms Used