Graph algebra

The concept of a graph algebra was introduced by G.F. McNulty and C.R. Shallon in 1983. 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 concerning, for example, dualities, equational theories (see equational theory), flatness, groupoid rings (see groupoid (algebra) and ring (mathematics)), topologies, varieties (see variety (universal algebra)), finite state automata or finite state machines, 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.

Deli'c, D. (2001). "Finite bases for flat graph algebras". J.~Algebra 246, 453-469.

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.

Lee, S.-M. (1988). "Graph algebras which admit only discrete topologies". Congr. Numer. 64, 147-156.

Lee, S.-M. (1991). "Simple graph algebras and simple rings". Southeast Asian Bull. Math. 15(2), 117-121.