HOMOMORPHISMS OF GRAPHS AND AUTOMATA.
Abstract
A homomorphism of a graph G onto a graph G' is a function phi from the set of points of G onto the set of points of G' such that whenever two points a and b are adjacent in G, their images, a phi and b phi are adjacent in G'. The concept of a homomorphism of an algebra or of a relational system has been defined and studied for many years, yet the concept of a homomorphism of a graph has not. Although several definitions of graphical homomorphisms have appeared in the literature, not many results have been obtained. In this paper the concept of a homomorphism of a graph is extensively studied. It is shown that the language of graphical homomorphisms is capable of expressing a variety of previously established results in graph theory in such a light as to enable these results to be generalized, proved as corollaries, or proved more simply. It is shown that the concept of a homomorphism of a graph is related to several other concepts in graph theory on the basis of which a number of altogether new results are established. It is also shown that in some cases the usefulness of homomorphisms in solving problems in graph theory is rather limited. The results that are obtained and the questions that are raised in this paper can be said to be either algebraic or graph theoretic in nature. However, an emphasis is placed upon obtaining graph theoretic results. Consequently, there are very few purely algebraic results in this paper; the portions of this work which are algebraic are almost entirely foundational in nature. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1966
- Accession Number
- AD0637000
Entities
People
- Stephen T. Hedetniemi
Organizations
- University of Michigan