# What is this operation on graphs called?

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?

• I do not know if this has a name but it reminds me of desingularisation of a point in an algebraic variety (with $H$ playing the role of a projective space glued at the singular point). Commented Sep 17, 2010 at 10:55
• I've seen the name "multiplication of vertices" used for the special case when H is an empty graph. I think this terminology goes back to Berge, but I would have to check. Commented Sep 17, 2010 at 14:09

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

• You confirm my impression that authors use ad hoc ways to describe this operation. I might just go by "blowing up of $G$ at $v$ by $H$". Commented Sep 17, 2010 at 12:48

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.

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).