Graph algebra with addition and multiplication

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

Tags:

Graph Theory

Reference Request

Abstract Algebra

Related

How to show the existence of the limit $\lim_{n\to \infty}\frac{x_n}{n}$ if $x_n$ satisfy $x^{-n}=\sum_{k=1}^\infty (x+k)^{-n}$? Why are $C^\infty_p\neq C^\infty_q$ when $p\neq q$? Homomorphic image of modular lattice is modular? The limit $\lim_{x \to 0-} \frac{e^{-x^2}}{\sqrt{\pi}} \int_0^\infty e^{-t^2/4} \frac{e^{2x} \cos t-1}{e^{4x}-2e^{2x} \cos t+1 } dt$ What does $\sum_{n=1}^\infty\frac{1}{\sqrt n(n+1)}$ converge to exactly? A conjecture related to any triangle If $d(x,y)$ is a metric on $X$, then $d'(x,y)=\frac{d(x,y)}{1 + d(x,y)}$ and $d(x,y)$ generates the same topology. Why can't we prove consistency of ZFC like we can for PA? Show that $x_n = \sqrt{\sum_{k=1}^n\left(\frac{k+1}{k}\right)^2} - \sqrt n$ is a bounded sequence. $(x,y)\subset \mathbb Q[x,y]$ is not a principal ideal Find all functions such that $f(x^2+y^2f(x))=xf(y)^2-f(x)^2$ Evaluating $\int_{0}^{2\pi}x^2\ln^2(1-\cos x)dx$

Recent Posts