Suvarna Garge (Editor)

Graph algebra

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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 in (McNulty & Shallon 1983), and has seen many uses in the field of universal algebra since then.

Contents

Definition

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

  • x y = x if x , y ∈ V , ( x , y ) ∈ E
  • x y = 0 if x , y ∈ V ∪ { 0 } , ( x , y ) ∉ E .

    • 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 (Davey et al. 2000), equational theories (Pöschel 1989), flatness (Delić 2001), groupoid rings (Lee 1991), topologies (Lee 1988), varieties (Oates-Williams 1984), finite state automata (Kelarev, Miller & Sokratova 2005), finite state machines (Kelarev & Sokratova 2003), tree languages and tree automata (Kelarev & Sokratova 2001) etc.

    References

    Graph algebra Wikipedia
    (Text) CC BY-SA