Graph algebra explained

In mathematics, especially in the fields of universal algebra and graph theory, a graph algebra is a way of giving a directed graph an algebraic structure. It was introduced by McNulty and Shallon, and has seen many uses in the field of universal algebra since then.

Definition

Let be a directed graph, and an element not in . The graph algebra associated with has underlying set

V \cup \{ 0 \} , and is equipped with a multiplication defined by the rules

• if

x,y \in V and (x,y) \in E ,

• if

x,y \in V \cup \{ 0 \} and (x,y)\notin E .

Applications

This notion has made it possible to use the methods of graph theory in universal algebra and several other areas of discrete mathematics and computer science. Graph algebras have been used, for example, in constructions concerning dualities, equational theories, flatness, groupoid rings, topologies, varieties, finite-state machines,tree languages and tree automata, etc.

See also

• Group algebra (disambiguation)
• Incidence algebra
• Path algebra

Works cited

• Dualizability and graph algebras . Davey . Brian A. . Idziak . Pawel M. . Lampe . William A. . McNulty . George F. . . 2000 . 214 . 1 . 145–172 . 10.1016/S0012-365X(99)00225-3 . 0012-365X . 1743633. free .
• Finite bases for flat graph algebras . Delić . Dejan . . 2001 . 246 . 1 . 453–469 . 10.1006/jabr.2001.8947 . 0021-8693 . 1872631 . free.
• Languages recognized by two-sided automata of graphs . Kelarev . A.V. . Miller . M. . Sokratova . O.V. . Proc. Estonian Akademy of Science . 2005 . 54 . 1 . 46–54 . 1736-6046 . 2126358.
• Directed graphs and syntactic algebras of tree languages . Kelarev . A.V. . Sokratova . O.V. . J. Automata, Languages & Combinatorics . 2001 . 6 . 3 . 305–311 . 1430-189X . 1879773.
• On congruences of automata defined by directed graphs . Kelarev . A.V. . Sokratova . O.V. . Theoretical Computer Science . 2003 . 301 . 1–3 . 31–43 . 10.1016/S0304-3975(02)00544-3 . 0304-3975 . 1975219.
• Graph algebras which admit only discrete topologies . Lee . S.-M. . Congr. Numer . 1988 . 64 . 147–156 . 1736-6046 . 0988675.
• Simple graph algebras and simple rings . Lee . S.-M. . Southeast Asian Bull. Math . 1991 . 15 . 2 . 117–121 . 0129-2021 . 1145431.
• Book: Inherently nonfinitely based finite algebras . McNulty . George F. . Shallon . Caroline R. . 1983 . Universal algebra and lattice theory (Puebla, 1982) . Freese . Ralph S. . Garcia . Octavio C. . . Berlin, New York City . 1004 . Lecture Notes in Math. . pp. 206–231 . . 10.1007/BFb0063439 . 10338.dmlcz/102157 . 978-354012329-3 . 716184 . free.
• On the variety generated by Murskiĭ's algebra . Oates-Williams . Sheila . Sheila Oates Williams . . 1984 . 18 . 2 . 175–177 . 10.1007/BF01198526 . 0002-5240 . 743465 . 121598599.
• The equational logic for graph algebras . Pöschel . R. . Z. Math. Logik Grundlag. Math. . 1989 . 35 . 3 . 273–282 . 10.1002/malq.19890350311 . 1000970.

Further reading

• Book: Kelarev, A.V. . Graph Algebras and Automata . 2003 . . New York City . registration . . 0-8247-4708-9 . 2064147 . none.
• Subvarieties of varieties generated by graph algebras . Kiss . E.W. . Pöschel . R. . Pröhle . P. . Acta Sci. Math . 1990 . 54 . 1–2 . 57–75 . 1073419 . none.
• Book: Raeburn, Iain . Graph algebras . 2005 . . 978-082183660-6 . none.