Graph Theory and Computing

List of ContributorsPrefaceAlternating Chain Methods: A Survey 1. Historical Background 2. The Maximum Matching Problem 3. The Maximum c-Matching Problem 4. The Maximum Stable Set Problem ReferencesThe Average Height of Planted Plane TreesHow to Number a Graph 1. A Statement of the Problem 2. A Context for the Problem 3. A History of Subproblems 4. Necessary Conditions for Graceful Graphs 5. Classes of Graceful Graphs 6. Some General Questions 7. Euclidean Models and Complete Graphs 8. Numbered Graphs and Difference Sets 9. Summary of Unsolved Problems 10. PostscriptEvolution of the Path Number of a Graph: Covering and Packing in Graphs, II 1. History 2. Results on the Path Number 3. The Unrestricted Path Number 4. Unsolved Problems ReferencesThe Production of Graphs by Computer 1. Introduction 2. Definitions and Terminology 3. Problems 4. Representation and Identification of Graphs in a Computer 5. Production of Simple Graphs 6. Production of Star Topologies 7. Production of Stars Having a Given Topology ReferencesA Graph-Theoretic Programming Language 1. Introduction 2. Design Considerations 3. FORTRAN Characteristics of GTPL 4. The Graph-Theoretical Statements of GTPL 5. Notes on Graph Theory Algorithms 6. Sample Programs 7. Concluding Remarks ReferencesEntropy of Transformed Finite-State Automata and Associated Languages 1. Introduction 2. Preliminaries 3. S Transformation of Automata 4. Entropy of S-Transformed Automata ReferencesCounting Hexagonal and Triangular Polyominoes 1. Introduction 2. Bounding Hexagons 3. Symmetries 4. Counting Algorithm 5. Performance, Results, and Omissions 6. Asymptotic Behavior ReferencesSymmetry of Cubical and General Polyominoes 1. Hypercubic Polyominoes and Their Symmetry 2. The Hyperoctahedral Group Od 3. The Existence of Models 4. Cubical Counts ReferencesGraph Coloring Algorithms 1. Introduction 2. Sequential Vertex Colorings 3. 5 Coloring Planar Graphs 4. Coloring Random Graphs ReferencesAlgebraic Isomorphism Invariants for Graphs of Automata 1. Introduction 2. Finite Automata and Transition Graphs 3. Algebraic Isomorphism Invariants 4. Disconnected Graphs and Elementary Divisors 5. Permutation Graphs 6. Forests 7. Arbitrary Transition Graphs ReferencesThe Coding of Various Kinds of Unlabeled Trees 1. Introduction: Coding in General 2. Definitions 3. Binary Codes for Planted Plane Trees 4. Binary Codes for Plane Rooted Trees 5. Binary Codes for Rooted Trees 6. The Decoding Algorithm 7. Binary Codes for Unrooted Trees 8. A Streamlined Algorithm for Coding Unrooted Trees 9. Some Properties of Tree Codes 10. Canonical Labelings 11. Valency Codes 12. Unrooted Trees Again ReferencesA Graph-Theoretic Study of the Numerical Solution of Sparse Positive Definite Systems of Linear Equations 1. Introduction 2. The Elimination Process 3. Triangulated Graphs 4. Optimal Ordering and Algorithms ReferencesIntelligent Graphs: Networks of Finite Automata Capable of Solving Graph Problems 1. Introduction to Myopic Algorithms 2. Finite Graphs and Finite Automata 3. Elementary Problem-Solving Automata 4. More Complex Problems ReferencesAn Algorithm for a General Constrained Set Covering Problem 1. The General Constrained Set Covering Problem 2. Notation and Main Concepts 3. The Algorithm ReferencesTripartite Path Numbers 1. Introduction 2. Elementary Results 3. Extensions of Previous Algorithms 4. The Exceptional Case 5. The Complete n-Partite Graph ReferencesNon-Hamiltonian Planar MapsA Top-Down Algorithm for Constructing Nearly Optimal Lexicographic Trees 1. Introduction 2. An Application 3.