What is this operation on graphs called?

Question

I am currently studying certain infinite graphs in terms of their finite induced subgraphs. For the graphs that I am interested in the class of finite induced subgraphs is closed under the following operation:

Given two graphs $G=(V(G),E(G))$ and $H=(V(H),E(H))$ and a vertex $v$ of $G$, let $G\otimes_v H$ (notation invented on the spot by myself) be the graph on the disjoint union of $V(G)\setminus\{v\}$ and $V(H)$ in which two vertices $x$ and $y$ are connected by an edge iff one of the following holds:

(1) $x,y\in V(G)\setminus\{v\}$ and $\{x,y\}\in E(G)$.

(2) Exactly one of $x$ and $y$ is in $V(H)$, say $y$ (wlog), and $\{x,v\}\in E(G)$.

(3) $\{x,y\}\in E(H)$.

In other words, the vertex $v$ of $G$ is replaced by a copy of $H$, and every vertex $w$ of $G$ different from $v$ is connected to all vertices of the copy of $H$ if $w$ and $v$ are connected in $G$. Otherwise $w$ is not connected to any of the vertices of the copy of $H$.
(Note that I am only doing this at a single vertex of $G$, not all of them. Otherwise I would get the wreath product or lexicographic product as mentioned in Nathann Cohen's answer below.)

Since this is a natural operation between graphs (with a distinguished vertex of the first graph), I would guess this has a name. If yes, how is this called?

Answer 1

I feel a bit stupid, but even though I have met this operation many, many times, I do not remember having ever seen it called by a specific name... The most common I saw used was "blow up a vertex v with a graph H", the adjacencies between the vertices of the copy of $H$ being as you described.

The two formal operations it makes me think of are the Lexicographic product of graphs, though in this case you are replacing ALL the vertices by a copy of a special graph, or the Modular decomposition (the vertices $S$ from a graph $H$ replacing the vertex $v$ in a graph $G$ are a module of your graph $G$ – they can not be told apart from outside of $S$).

I tried to look for papers where this name may have been mentioned, as the operation was used... I ended up on the Open Problem Garden page about the Erdős–Hajnal conjecture, where "Blowing up" is used. In Ramsey-type Theorems with Forbidden Subgraphs, the authors (Noga Alon, János Pach and József Solymosi) replace a vertex $v$ with a copy of a graph (follows a description of the adjacencies)...

(Well, this is not really an answer, just a long way to say that I have no idea :-D)

Nathann

Answer 2

After looking through some of the literature, it seems that a common name for this operation is substitution: the graph $H$ is substituted for the vertex $v$ of the graph $G$.
This is what Lovasz calls the operation in his paper where he proves the perfect graph theorem (PGT: complements of perfect graphs are perfect).
There is also the Lovasz substitution lemma which says that when a perfect graph is substituted for a vertex of a perfect graph, then the resulting graph is again perfect.

Answer 3

This reminds me of "Pachner moves". In the case where $H$ is a complete graph $K_n$, then your operation is the 1-to-n Pachner move, or 1-to-n expansion (for example here is a paper that uses this language). This suggests the terminology "$v$ to $H$ expansion", and then you could define "$H$ to $v$ contraction" similarly (unfortunately I don't think this is standard).