Graph congruences and what they connote.

The algebraic notion of a "congruence" seems to be foreign to contemporary graph theory. We propound that it need not be so by developing a theory of congruences of graphs: a congruence on a graph G = (V, E) being a pair (∼, ) of which ∼ is an equivalence relation on V and is a set of unordered pairs of vertices of G with a special relationship to ∼ and E. Kernels and quotient structures are used in this theory to develop homomorphism and isomorphism theorems which remind one of similar results in an algebraic context. We show that this theory can be applied to deliver structural decompositions of graphs into "factor" graphs having very special properties, such as the result that each graph, except one, is a subdirect product of graphs with universal vertices. In a final section, we discuss corresponding concepts and briefly describe a corresponding theory for graphs which have a loop at every vertex and which we call loopy graphs. They are in a sense more "algebraic" than simple graphs, with their meet-semilattices of all congruences becoming complete algebraic lattices. [ABSTRACT FROM AUTHOR]