10
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ 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). $\endgroup$ Sep 17, 2010 at 10:55
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 17, 2010 at 14:09

3 Answers 3

7
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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$". $\endgroup$ Sep 17, 2010 at 12:48
6
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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