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}$.

This notion has made it possible to use the methods of graph theory in universal algebra and several other directions of discrete mathematics and computer science. Graph algebras have been used, for example, in constructions concerning 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.

Oates-Williams, S. (1984). "On the variety generated by Murskii's algebra". Algebra Universalis 18(2), 175-177.

P"oschel, R. (1989). "The equational logic for graph algebras". Z. Math. Logik Grundlag. Math. 35(3), 273-282.