Article

Graph congruences and what they connote

Published in: Quaestiones Mathematicae
Volume 41 , issue 8 , 2018 , pages: 1045–1059

DOI: 10.2989/16073606.2017.1419388

Author(s): Izak Broere Department of Mathematics and Applied Mathematics, South Africa , Johannes Heidema Emeritus, Department of Mathematical Sciences, , Lou Pretorius Department of Mathematics and Applied Mathematics, South Africa

Keywords: 05C25 , 05C76 , 05C25 , 05C76

Download full text Get new issue alerts

Abstract

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.

« Two-sided inequalities for the Struve and Lommel functions

A class of commutative semirings with stable range 2 »