Pseudo-product

Pseudo-product --- псевдопроизведение.

Let [math]\displaystyle{ G }[/math] and [math]\displaystyle{ G' }[/math] be simple graphs on the same set of vertices [math]\displaystyle{ V(G) = V(G') = V }[/math], where [math]\displaystyle{ |V| = n \geq 1 }[/math]. Define the pseudo product of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ G' }[/math] to be the simple graph [math]\displaystyle{ G * G' }[/math] on the vertex set [math]\displaystyle{ V }[/math] with the edge set [math]\displaystyle{ E(G * G') = E(G) \cup E(G') \cup E^{\ast} }[/math], where

[math]\displaystyle{ E^{\ast} = \{\{u,v\}: \; \exists w \in V: \; \{u,w\} \in E(G), \{w,v\} \in E(G'), }[/math] [math]\displaystyle{ \mbox{ and }\exists w' \in V: \; \{u,w'\} \in E(G'), \{w',v\} \in E(G)\}. }[/math]

For a simple graph [math]\displaystyle{ G }[/math] and nonnegative integers [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math], we have

[math]\displaystyle{ G^{s} * G^{t} = G^{s+t}. }[/math]

In particular, the pseudo product is an associative operation on the set [math]\displaystyle{ \{G^{k}: \; k \in \{0,1,2, \ldots,\}\} }[/math] for any fixed simple graph [math]\displaystyle{ G }[/math].