Jump to content

Graph algebra

Edit links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 23:09, 29 May 2021 (Sheila Oates Williams). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
This article is about the mathematical concept of Graph Algebras. For "Graph Algebra" as used in the social sciences, see Graph algebra (social sciences).

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,[1] and has seen many uses in the field of universal algebra since then.

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 , and is equipped with a multiplication defined by the rules

  • xy = x if and ,
  • xy = 0 if and .

Applications

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,[2] equational theories,[3] flatness,[4] groupoid rings,[5] topologies,[6] varieties,[7] finite state automata,[8] finite state machines,[9] tree languages and tree automata,[10] etc.

See also

Works cited

  1. ^ 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 9783540123293. MR 0716184 – via Internet Archive.
  2. ^ 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.
  3. ^ 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.
  4. ^ 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.
  5. ^ Lee, S.-M. (1991). "Simple graph algebras and simple rings". Southeast Asian Bull. Math. 15 (2): 117–121. ISSN 0129-2021. MR 1145431.
  6. ^ Lee, S.-M. (1988). "Graph algebras which admit only discrete topologies". Congr. Numer. 64: 147–156. ISSN 1736-6046. MR 0988675.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ 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.

Further reading

Retrieved from "https://en.wikipedia.org/w/index.php?title=Graph_algebra&oldid=1025849261"