View source for Graph algebra

{{about|the mathematical concept of Graph Algebras|"Graph Algebra" as used in the social sciences|Graph algebra (social sciences)}}
{{Use shortened footnotes|date=May 2021}}

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,{{sfn|McNulty|Shallon|1983|loc=[https://archive.org/details/universalalgebra0000unse/page/206 pp. 206–231]}} and has seen many uses in the field of universal algebra since then.

== Definition ==
Let {{math|1=''D'' = (''V'', ''E'')}} be a directed [[graph (data structure)|graph]], and {{math|0}} an element not in {{mvar|V}}. The graph algebra associated with {{mvar|D}} has underlying set <math>V \cup \{0\}</math>, and is equipped with a multiplication defined by the rules
* {{math|1=''xy'' = ''x''}} if <math>x,y \in V</math> and <math>(x,y) \in E</math>,
* {{math|1=''xy'' = 0}} if <math>x,y \in V \cup \{0\}</math> and <math>(x,y)\notin E</math>.

== 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 [[Dual (category theory)|dualities]],{{sfn|Davey|Idziak|Lampe|McNulty|2000|pp=145–172}} [[equational theory|equational theories]],{{sfn|Pöschel|1989|pp=273–282}} [[flatness (systems theory)|flatness]],{{sfn|Delić|2001|pp=453–469}} [[groupoid (algebra)|groupoid]] [[ring (mathematics)|rings]],{{sfn|Lee|1991|pp=117–121}} [[topology|topologies]],{{sfn|Lee|1988|pp=147–156}} [[variety (universal algebra)|varieties]],{{sfn|Oates-Williams|1984|pp=175–177}}  [[finite-state machine]]s,{{sfn|Kelarev|Miller|Sokratova|2005|pp=46–54}}{{sfn|Kelarev|Sokratova|2003|pp=31–43}}
tree languages and [[tree automata]],{{sfn|Kelarev|Sokratova|2001|pp=305–311}} etc.

== See also ==
* [[Group algebra (disambiguation)]]
* [[Incidence algebra]]
* [[Path algebra]]

==Citations==
{{Reflist|20em}}

==Works cited==
{{refbegin|35em}}
*{{Cite journal | title = Dualizability and graph algebras
 | last1 = Davey | first1 = Brian A.
 | last2 = Idziak | first2 = Pawel M.
 | last3 = Lampe | first3 = William A.
 | last4 = McNulty | first4 = George F.
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | year = 2000 | volume = 214 | issue = 1 | pages = 145–172
 | doi = 10.1016/S0012-365X(99)00225-3 | issn = 0012-365X | mr = 1743633
| doi-access = free }}
*{{Cite journal | title = Finite bases for flat graph algebras
 | last = Delić | first = Dejan
 | journal = [[Journal of Algebra]]
 | year = 2001 | volume = 246 | issue = 1 | pages = 453–469
 | doi = 10.1006/jabr.2001.8947 | issn = 0021-8693 | mr = 1872631
 | doi-access = free
}}
*{{Cite journal | title = Languages recognized by two-sided automata of graphs
 | last1 = Kelarev | first1 = A.V.
 | last2 = Miller | first2 = M.
 | last3 = Sokratova | first3 = O.V.
 | journal = Proc. Estonian Akademy of Science
 | year = 2005 | volume = 54 | issue = 1 | pages = 46–54
 | issn = 1736-6046 | mr = 2126358
}}
*{{Cite journal | title = Directed graphs and syntactic algebras of tree languages
 | last1 = Kelarev | first1 = A.V.
 | last2 = Sokratova | first2 = O.V.
 | journal = J. Automata, Languages & Combinatorics
 | year = 2001 | volume = 6 | issue = 3 | pages = 305–311
 | issn = 1430-189X | mr = 1879773
}}
*{{Cite journal | title = On congruences of automata defined by directed graphs
 | last1 = Kelarev | first1 = A.V.
 | last2 = Sokratova | first2 = O.V.
 | journal = Theoretical Computer Science
 | year = 2003 | volume = 301 | issue = 1–3 | pages = 31–43
 | url = https://eprints.utas.edu.au/157/1/congruences.pdf
 | doi = 10.1016/S0304-3975(02)00544-3 | issn = 0304-3975 | mr = 1975219
}}
*{{Cite journal | title = Graph algebras which admit only discrete topologies
 | last = Lee | first = S.-M.
 | journal = Congr. Numer
 | year = 1988 | volume = 64 | pages = 147–156
 | issn = 1736-6046 | mr = 0988675
}}
*{{Cite journal | title = Simple graph algebras and simple rings
 | last = Lee | first = S.-M.
 | journal = Southeast Asian Bull. Math
 | year = 1991 | volume = 15 | issue = 2 | pages = 117–121
 | issn = 0129-2021 | mr = 1145431
}}
*{{Cite book| chapter = Inherently nonfinitely based finite algebras
 | last1 = McNulty | first1 = George F.
 | last2 = Shallon | first2 = Caroline R.
 | year = 1983
 | title = Universal algebra and lattice theory (Puebla, 1982)
 | editor1-last = Freese | editor1-first = Ralph S.
 | editor2-last = Garcia | editor2-first = Octavio C.
 | publisher = [[Springer-Verlag]] | location = Berlin, New York City
 | volume = 1004 | series = Lecture Notes in Math.
 | at = [https://archive.org/details/universalalgebra0000unse/page/206 pp. 206–231]
 | url = https://archive.org/details/universalalgebra0000unse | via = [[Internet Archive]]
 | doi = 10.1007/BFb0063439 | hdl = 10338.dmlcz/102157 | isbn = 978-354012329-3 | mr = 716184
 | hdl-access = free
}}
*{{Cite journal | title = On the variety generated by Murskiĭ's algebra
 | last = Oates-Williams | first = Sheila
 | author-link = Sheila Oates Williams
 | journal = [[Algebra Universalis]]
 | year = 1984 | volume = 18 | issue = 2 | pages = 175–177
 | doi = 10.1007/BF01198526 | issn = 0002-5240 | mr = 743465 | s2cid = 121598599
}}
*{{Cite journal | title = The equational logic for graph algebras
 | last = Pöschel | first = R.
 | journal = Z. Math. Logik Grundlag. Math.
 | year = 1989 | volume = 35 | issue = 3 | pages = 273–282
 | doi = 10.1002/malq.19890350311 | mr = 1000970
}}
{{refend}}

==Further reading==
{{refbegin}}
*{{Cite book| title = Graph Algebras and Automata
 | last = Kelarev | first = A.V. | year = 2003
 | publisher = [[Marcel Dekker]] | place = New York City
 | url = https://archive.org/details/graphalgebrasaut0000kela | url-access = registration | via = [[Internet Archive]]
 | isbn = 0-8247-4708-9 | mr = 2064147
 | ref = none
}}
*{{cite journal | title = Subvarieties of varieties generated by graph algebras
 | last1 = Kiss | first1 = E.W.
 | last2 = Pöschel | first2 = R.
 | last3 = Pröhle | first3 = P.
 | journal = Acta Sci. Math.
 | year = 1990 | volume = 54 | issue = 1–2 | pages = 57–75
 | mr = 1073419
 | ref = none
}}
*{{Cite book| title = Graph algebras
 | last = Raeburn | first = Iain | year = 2005
 | publisher = [[American Mathematical Society]]
 | isbn = 978-082183660-6
 | ref = none
}}
{{refend}}

[[Category:Graph theory]]
[[Category:Universal algebra]]