Some new graph operations in graph theory.

Question

I was just going through following link on wiki about the graph operations:

https://en.wikipedia.org/wiki/Graph_operations.

Just curious to know if there any other graph operations that are not defined in the above link. It would be kind of you to help me. Thanks a lot for helping me.

Answer 1

For an explicit example of a graph operation not (currently) listed on the wiki page, consider the wreath product. While usually defined for algebraic objects like groups, it's also possible to define a wreath product for graphs. The following definition can be found in [1] which goes on to further generalize the operation to a generalized wreath product.

Let $\mathcal{G}_1 = (V_1, E_1)$ and $\mathcal{G}_2 = (V_2, E_2)$ be two finite graphs. The wreath product $\mathcal{G}_1 \wr \mathcal{G}_2$ is the graph with vertex set $V_2^{V_1} \times V_1 = \{(f, v) \vert f:V_1 \rightarrow V_2, v\in V_1\}$ where two vertices $(f,v)$ and $(f', v')$ are connected by an edge if:

1) (edges of the first type) either $v=v'=: \overline{v}$ and $f(w) = f(w')$ for every $w \neq \overline{v}$, and $f(\overline{v}) \sim f'(\overline{v})$ in $\mathcal{G}_2$;

2) (edges of the second type) or $f(w) = f'(w)$, for every $w\in V_1$, and $v\sim v'$ in $\mathcal{G}_1$.

EDITED TO ADD:

Another graph operation not currently listed on the wiki page is transitive closure. This one is a little surprising to me since this one is much more elementary than the wreath product.

1. Donno, Alfredo. "Generalized wreath products of graphs and groups." Graphs and Combinatorics 31.4 (2015): 915-926.

Answer 2

Hint: Many years ago I had to do some work with hypergraphs which you won't find at the referred Wiki-page with focus operation on graphs. It is instead considered to be some kind of generalisation of graphs.

Maybe you are also interested in the Wiki-page extensions and generalisations of graphs, since for instance coloring or labeling of graphs might also be considered as operations on graphs.

Answer 3

I'm pretty sure Wikipedia has all of them in the article, if not then at least one guy would have added it.