Accession Number : AD0683295

Title :   ON CLASSES OF GRAPHS DEFINED BY SPECIAL CUTSETS OF LINES.

Descriptive Note : Technical rept.,

Corporate Author : IOWA UNIV IOWA CITY DEPT OF MATHEMATICS

Personal Author(s) : Hedetniemi,Stephen

Report Date : JAN 1969

Pagination or Media Count : 36

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)

Descriptors :   (*GRAPHICS, GROUPS(MATHEMATICS)), COMBINATORIAL ANALYSIS, SET THEORY, PERMUTATIONS, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE