ON CLASSES OF GRAPHS DEFINED BY SPECIAL CUTSETS OF LINES.
Abstract
A new method is given for studying graphs. Generally speaking this involves decomposing a graph into two disjoint subgraphs which are connected by special sets of lines. Four types of connections between these subgraphs are considered, i.e. those for which the set of connecting lines describes a function, a homomorphism, a permutation, or an automorphism. This manner of decomposing a graph is thought to be useful for studying a wide variety of parameters and properties of graphs. To illustrate this, results are obtained relating to such concepts as arboricity, thickness, biparticity, and chromatic number. A method is derived for constructing new classes of critical graphs, and several isomorphism theorems for classes of permutation graphs are given, one of which involves the group theoretic concept of a double coset. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1969
- Accession Number
- AD0683295
Entities
People
- Stephen Hedetniemi
Organizations
- University of Iowa