• Images
• Videos
• Documents
• Books
• Articles

Definition

Let D = (V, E) be a directed graph, and 0 an element not in V. The graph algebra associated with D has underlying set V ∪ { 0 } {\displaystyle V\cup \{0\}} , and is equipped with a multiplication defined by the rules

• xy = x if x , y ∈ V {\displaystyle x,y\in V} and ( x , y ) ∈ E {\displaystyle (x,y)\in E} ,
• xy = 0 if x , y ∈ V ∪ { 0 } {\displaystyle x,y\in V\cup \{0\}} and ( x , y ) ∉ E {\displaystyle (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

Citations

Works cited

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

Further reading

• Kelarev, A.V. (2003). Graph Algebras and Automata. New York City: Marcel Dekker. ISBN 0-8247-4708-9. MR 2064147 – via Internet Archive.
• Kiss, E.W.; Pöschel, R.; Pröhle, P. (1990). "Subvarieties of varieties generated by graph algebras". Acta Sci. Math. 54 (1–2): 57–75. MR 1073419.
• Raeburn, Iain (2005). Graph algebras. American Mathematical Society. ISBN 978-082183660-6.

References

1. McNulty & Shallon 1983, pp. 206–231. - McNulty, George F.; Shallon, Caroline R. (1983). "Inherently nonfinitely based finite algebras". In Freese, Ralph S.; Garcia, Octavio C. (eds.). Universal algebra and lattice theory (Puebla, 1982). Lecture Notes in Math. Vol. 1004. Berlin, New York City: Springer-Verlag. pp. 206–231. doi:10.1007/BFb0063439. hdl:10338.dmlcz/102157. ISBN 978-354012329-3. MR 0716184 – via Internet Archive. https://archive.org/details/universalalgebra0000unse ↩

2. Davey et al. 2000, pp. 145–172. - Davey, Brian A.; Idziak, Pawel M.; Lampe, William A.; McNulty, George F. (2000). "Dualizability and graph algebras". Discrete Mathematics. 214 (1): 145–172. doi:10.1016/S0012-365X(99)00225-3. ISSN 0012-365X. MR 1743633. https://doi.org/10.1016%2FS0012-365X%2899%2900225-3 ↩

3. Pöschel 1989, pp. 273–282. - Pöschel, R. (1989). "The equational logic for graph algebras". Z. Math. Logik Grundlag. Math. 35 (3): 273–282. doi:10.1002/malq.19890350311. MR 1000970. https://doi.org/10.1002%2Fmalq.19890350311 ↩

4. Delić 2001, pp. 453–469. - Delić, Dejan (2001). "Finite bases for flat graph algebras". Journal of Algebra. 246 (1): 453–469. doi:10.1006/jabr.2001.8947. ISSN 0021-8693. MR 1872631. https://doi.org/10.1006%2Fjabr.2001.8947 ↩

5. Lee 1991, pp. 117–121. - Lee, S.-M. (1991). "Simple graph algebras and simple rings". Southeast Asian Bull. Math. 15 (2): 117–121. ISSN 0129-2021. MR 1145431. https://search.worldcat.org/issn/0129-2021 ↩

6. Lee 1988, pp. 147–156. - Lee, S.-M. (1988). "Graph algebras which admit only discrete topologies". Congr. Numer. 64: 147–156. ISSN 1736-6046. MR 0988675. https://search.worldcat.org/issn/1736-6046 ↩

7. Oates-Williams 1984, pp. 175–177. - Oates-Williams, Sheila (1984). "On the variety generated by Murskiĭ's algebra". Algebra Universalis. 18 (2): 175–177. doi:10.1007/BF01198526. ISSN 0002-5240. MR 0743465. S2CID 121598599. https://doi.org/10.1007%2FBF01198526 ↩

8. Kelarev, Miller & Sokratova 2005, pp. 46–54. - Kelarev, A.V.; Miller, M.; Sokratova, O.V. (2005). "Languages recognized by two-sided automata of graphs". Proc. Estonian Akademy of Science. 54 (1): 46–54. ISSN 1736-6046. MR 2126358. https://search.worldcat.org/issn/1736-6046 ↩

9. Kelarev & Sokratova 2003, pp. 31–43. - Kelarev, A.V.; Sokratova, O.V. (2003). "On congruences of automata defined by directed graphs" (PDF). Theoretical Computer Science. 301 (1–3): 31–43. doi:10.1016/S0304-3975(02)00544-3. ISSN 0304-3975. MR 1975219. https://eprints.utas.edu.au/157/1/congruences.pdf ↩

10. Kelarev & Sokratova 2001, pp. 305–311. - Kelarev, A.V.; Sokratova, O.V. (2001). "Directed graphs and syntactic algebras of tree languages". J. Automata, Languages & Combinatorics. 6 (3): 305–311. ISSN 1430-189X. MR 1879773. https://search.worldcat.org/issn/1430-189X ↩