Congruences and subdirect representations of graphs

Stefan Veldsman

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


congruence on a graph, quotient graph, subdirect product of graphs, subdirectly irreducible graph, Birkhoff's theorem

Full Text:

PDF

DOI: 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

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

View EJGTA Stats