Substitution of a graph

Substitution of a graph --- подстановка графа.

1. A substitution of a graph [math]\displaystyle{ G }[/math] for a vertex [math]\displaystyle{ x }[/math] of a graph [math]\displaystyle{ H }[/math] (supposing [math]\displaystyle{ G }[/math] and [math]\displaystyle{ H }[/math] are vertex-disjoint) is the following operation: we remove [math]\displaystyle{ x }[/math] from [math]\displaystyle{ H }[/math] and replace each edge [math]\displaystyle{ (x,y) }[/math] ([math]\displaystyle{ y \in V(G) - \{x\} }[/math]) by the [math]\displaystyle{ |V(G)| }[/math] edges connecting [math]\displaystyle{ y }[/math] to the vertices of [math]\displaystyle{ G }[/math].

2. Let [math]\displaystyle{ G }[/math] and [math]\displaystyle{ R }[/math] be two graphs over [math]\displaystyle{ \Sigma }[/math] (a finite set of node labels). Let [math]\displaystyle{ C \subseteq \Sigma \times V_{R} }[/math] be an embedding relation for [math]\displaystyle{ R }[/math], and let [math]\displaystyle{ u }[/math] be a node from [math]\displaystyle{ G }[/math]. The graph [math]\displaystyle{ G[u/_{C} R] }[/math] is obtained by replacing the node [math]\displaystyle{ u }[/math] by [math]\displaystyle{ R }[/math] with respect to [math]\displaystyle{ C }[/math] as follows:

• Let [math]\displaystyle{ J }[/math] be the union of [math]\displaystyle{ G }[/math] (without the node [math]\displaystyle{ u }[/math] and its incident edges) and a copy of [math]\displaystyle{ R }[/math] which is disjoint with [math]\displaystyle{ G }[/math].

• For each edge [math]\displaystyle{ (v,u) }[/math] from [math]\displaystyle{ G }[/math], add an edge [math]\displaystyle{ (v,w) }[/math] to the set of edges of [math]\displaystyle{ J }[/math] if and only if [math]\displaystyle{ (\phi(v),w) \in C }[/math]. The resulting graph is [math]\displaystyle{ G[u/_{C} R] }[/math].

Thus [math]\displaystyle{ G[u/_{C} R] }[/math] is obtained substituting [math]\displaystyle{ u }[/math] by [math]\displaystyle{ R }[/math] and establishing connections according to [math]\displaystyle{ C }[/math].