Congruences and subdirect representations of graphs
| Main Author: | Veldsman, Stefan; Department of Mathematics, Nelson Mandela University, Port Elizabeth, South Africa |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB
, 2020
|
| Subjects: | |
| Online Access: |
https://www.ejgta.org/index.php/ejgta/article/view/846 https://www.ejgta.org/index.php/ejgta/article/view/846/pdf_129 |
Daftar Isi:
- 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