### Congruences and subdirect representations of graphs

#### Abstract

A basic tool in universal algebra is that of a congruence. It has been shown that congruences can be defined for graphs with properties similar to their universal algebraic counterparts. In particular, a subdirect product of graphs and hence also a subdirectly irreducible graph, can be expressed in terms of graph congruences. Here the subdirectly irreducible graphs are determined explicitly. Using congruences, a graph theoretic version of the well-known Birkhoff Theorem from universal algebra is given. This shows that any non-trivial graph is a subdirect product of subdirectly irreducible graphs

#### Keywords

#### Full Text:

PDFDOI: http://dx.doi.org/10.5614/ejgta.2020.8.1.9

#### References

G. Birkhoff, Subdirect unions in universal algebra, Bull. Amer. Math. Soc. 50 (1944) 764 –768.

I. Broere, J. Heidema and L.M. Pretorius, Graph congruences and what they connote, Quaest. Math. 41 (2018), 1045–1058.

I. Broere, J. Heidema and S. Veldsman, Congruences and Hoehnke Radicals on Graphs, Dis- cuss. Math. Graph Theory. To appear.

B. Fawcett, Graphs and ultrapowers. PhD Thesis, McMaster University (1969).

E. Fried and R. Wiegandt, Connectednesses and disconnectednesses of graphs, Algebra Uni- versalis 5 (1975), 411–428.

B.J. Gardner and R. Wiegandt, The Radical Theory of Rings, Marcel Dekker Inc., New York (2004).

H.J. Hoehnke, Radikale in algemeinen Algebren, Mathematische Nachrichten 32 (1966), 347– 383.

G. Sabidussi, Subdirect representations of graphs. Coll. Math. Soc. Janos Bolyai 10 Infinite and finite sets (Kesztheley, Hungary, 1973), North Holland, Amsterdam 1199 - 1226 (1975).

### Refbacks

- There are currently no refbacks.

ISSN: 2338-2287

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.