Graph algebra

The concept of a graph algebra was introduced by G.F. McNulty and C.R. Shallon in [2]. Let ${\displaystyle D=(V,E)}$ be a directed graph (see Graph (data structure)), and let ${\displaystyle 0}$ be an element not in ${\displaystyle V}$. The graph algebra associated with ${\displaystyle D}$ is the set ${\displaystyle V\cup \{0\}}$ equipped with multiplication defined by the rules ${\displaystyle xy=x}$ if ${\displaystyle x,y\in V,(x,y)\in E}$, and ${\displaystyle xy=0}$ if ${\displaystyle x,y\in V\cup \{0\},(x,y)\notin E}$.

Graph algebras have been used in several directions of mathematics and computer science in constructions of various examples concerning dualities, varieties, finite state automata etc.

References

Davey, B.A.; Idziak, P.M.; Lampe W.A.; & McNulty, G.F. (2000). "Dualizability and graph algebras", Discrete Math. 214(1-3), 145-172.

McNulty, G.F.; & Shallon, C.R. (1983). "Inherently nonfinitely based finite algebras". In Universal Algebra and Lattice Theory (Puebla, 1982), Springer, Berlin, 206-231.

Kelarev, A.V. (2003). Graph Algebras and Automata. Marcel Dekker, New York. ISBN: 0-8247-4708-9.

Kelarev, A.V.; & Sokratova, O.V. (2003). "On congruences of automata defined by directed graphs", Theoretical Computer Science 301, 31-43.

Kiss, E.W.; P"oschel, R.; & Pr"ohle, P. (1990). "Subvarieties of varieties generated by graph algebras", Acta Sci. Math. (Szeged) 54(1-2), 57-75.