COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Graph Theory and Computing - 1st Edition - ISBN: 9781483231877, 9781483263120

Graph Theory and Computing

1st Edition

Editor: Ronald C. Read
eBook ISBN: 9781483263120
Imprint: Academic Press
Published Date: 1st January 1972
Page Count: 344
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.


Graph Theory and Computing focuses on the processes, methodologies, problems, and approaches involved in graph theory and computer science. The book first elaborates on alternating chain methods, average height of planted plane trees, and numbering of a graph. Discussions focus on numbered graphs and difference sets, Euclidean models and complete graphs, classes and conditions for graceful graphs, and maximum matching problem. The manuscript then elaborates on the evolution of the path number of a graph, production of graphs by computer, and graph-theoretic programming language. Topics include FORTRAN characteristics of GTPL, design considerations, representation and identification of graphs in a computer, production of simple graphs and star topologies, and production of stars having a given topology. The manuscript examines the entropy of transformed finite-state automata and associated languages; counting hexagonal and triangular polyominoes; and symmetry of cubical and general polyominoes. Graph coloring algorithms, algebraic isomorphism invariants for graphs of automata, and coding of various kinds of unlabeled trees are also discussed. The publication is a valuable source of information for researchers interested in graph theory and computing.

Table of Contents

List of Contributors


Alternating Chain Methods: A Survey

1. Historical Background

2. The Maximum Matching Problem

3. The Maximum c-Matching Problem

4. The Maximum Stable Set Problem


The Average Height of Planted Plane Trees

How 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. Postscript

Evolution 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


The 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


A 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


Entropy of Transformed Finite-State Automata and Associated Languages

1. Introduction

2. Preliminaries

3. S Transformation of Automata

4. Entropy of S-Transformed Automata


Counting Hexagonal and Triangular Polyominoes

1. Introduction

2. Bounding Hexagons

3. Symmetries

4. Counting Algorithm

5. Performance, Results, and Omissions

6. Asymptotic Behavior


Symmetry of Cubical and General Polyominoes

1. Hypercubic Polyominoes and Their Symmetry

2. The Hyperoctahedral Group Od

3. The Existence of Models

4. Cubical Counts


Graph Coloring Algorithms

1. Introduction

2. Sequential Vertex Colorings

3. 5 Coloring Planar Graphs

4. Coloring Random Graphs


Algebraic 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


The 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


A 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


Intelligent 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


An Algorithm for a General Constrained Set Covering Problem

1. The General Constrained Set Covering Problem

2. Notation and Main Concepts

3. The Algorithm


Tripartite Path Numbers

1. Introduction

2. Elementary Results

3. Extensions of Previous Algorithms

4. The Exceptional Case

5. The Complete n-Partite Graph


Non-Hamiltonian Planar Maps

A Top-Down Algorithm for Constructing Nearly Optimal Lexicographic Trees

1. Introduction

2. An Application

3. Basis of a Top-Down Algorithm

4. Algorithm for Nearly Optimal Lexicographic Trees

5. Choosing Parameters of the Algorithm

6. Time to Construct the Nearly Optimal Tree

7. Tests of the Algorithm

8. Summary




No. of pages:
© Academic Press 1972
1st January 1972
Academic Press
eBook ISBN:

About the Editor

Ronald C. Read

Ratings and Reviews