Graph algebra with addition and multiplication

Question

First of all apologies if this sounds like a stupid question to some. I read a month ago a presentation about how graphs could be endowed with addition and multiplication in some interesting ways and I can't find anything about it by googling, so I am resorting to your knowledge. Basically, and out of my memory so I might be wrong, starting from $G = (E,V), G' = (E',V')$ :

• addition was simply $G + G' = (E + E', V + V')$, with obvious meanings for edges and vertices addition (union of sets)
• multiplication was $G \times G' = (E + E' + V \times V', V + V')$. Basically, for each vertex $v$ of $V$, for any vertex $v'$ in $V'$, you add $(v, v')$ edge to $G + G'$.
• also if I remember well there was some distributivity law, maybe a(b+c) = ab + ac + bc

Does that ring any bell to anybody? Sorry again for the shallowness of the question. I am looking for the name of that particular algebra so I can google it and find more about it.

Answer 1

Finally found it back!! It is fairly recent work, dating around 5-10 years ago. So, the addition and multiplication are as defined in the question. However the distributivity law I mentioned does not hold but the standard distributivity laws do, i.e. $a(b+c) = ab + ac$. And the algebra is called Algebra of Parameterised Graphs with a corresponding Haskell package.

The multiplication can also be called connect or sequence and be noted as $\rightarrow$. The addition operation can also be called overlay. Denoting the empty graph by $\epsilon$ :

Properties of overlay:

• Identity: $$G + ε = G$$
• Commutativity: $$G1 + G2 = G2 + G1$$
• Associativity: $$(G1 + G2) + G3 = G1 + (G2 + G3)$$

Properties of sequence:

• Left and right identity: $$ε → G = G$$ $$G → ε = G$$
• Associativity: $$(G1 → G2) → G3 = G1 → (G2 → G3)$$

Other properties:

• Left and right distributivity: $$G1 → (G2 + G3) = G1 → G2 + G1 → G3$$ $$(G1 + G2) → G3 = G1 → G3 + G2 → G3$$
• Decomposition: $$G1 → G2 → G3 = G1 → G2 + G1 → G3 + G2 → G3$$

Answer 2

I am not entirely sure if this is what you had in mind, but this is one pretty standard construction of this sort. I have no idea concerning the name of this construction; I would call it "the semiring of isomorphism classes of objects of the distributive category of finite graphs".

---

One can define "addition" (or, better, coproduct) of graphs simply as a disconnected union. This operation is pretty natural, though, and can be defined as the most general, yet not too big graph that includes both original graphs.

Similarly, the product of two graphs is the most general, yet not too big graph that projects on both original graphs, also known as tensor product of graphs (there is also the cartesian product of graphs, which is different). The product of $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ happens to look like this: it's vertices are pairs of vertices of $G_1$ and $G_2$ (i.e. the cartesian product $V_1\times V_2$), and it's edges are $(x_1,x_2)-(y_1,y_2)$ if $x_1 - y_1$ is an edge of $G_1$ and $x_2-y_2$ is an edge of $G_2$.

Now, taking the set of all (isomorphism classes of finite) graphs, one could define operations $+$ and $\times$ on this set as specified above. These obey a lot of useful properties: both operations are associative, commutative, have a neutral element (empty graph for $+$ and a singleton without edges for $\times$), and the distributive law holds:

• $A \times (B + C) = A \times B + A \times C$

Division can be harder in this setting, though, and I believe that most graphs are "prime", i.e. cannot be decomposed into a product (do not take this too seriously, though, as this is just a belief), while decomposition into a sum is basically a decomposition into connected components.

---

Most links in the previous paragraphs refer to some general category-theoretic abstract nonsense for a solid reason: all this has nothing to do with graphs. The same construction can be performed on any category with all products & coproducts (but some arithmetic laws like distributivity may fail, but not in distributive categories).

For example, taking the category of finite sets gives us natural numbers with their usual $+$ and $\times$.

Taking the category of finite-dimensional vector spaces over some field gives something ridiculous: objects are still natural numbers, $+$ works as usual, but $\times$ coincides with $+$, and no distributivity here.

---

Also note that there do exist several entirely different constructions with related names, though they do not seem relevant to your question.

• Graph algebra
• Path algebra
• Incidence algebra