Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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). –  Roland Bacher Sep 17 '10 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. –  François G. Dorais Sep 17 '10 at 14:09
add comment

3 Answers

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 mentionned, as the operation was used... I ended up on this page abour the Erdos-Hajnal conjecture, where "Blowing up" is used. In this Ramsey-type Theorems with Forbidden Subgraphs, the autors (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)


share|improve this answer
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$". –  Stefan Geschke Sep 17 '10 at 12:48
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.