2
$\begingroup$

Suppose $v$ is a vertex in a graph $G$. Is there a name for the process of replacing $v$ with $d(v)$ (the degree of $v$) many vertices, one attached to each edge coming into $v$?

For instance if $V(K_3)=\{v_0,v_1,v_2\}$ are the vertices of the "triangle" graph, then doing my process at any one vertex would produce $P_3$, the path of length 3 (3 edges between 4 vertices).

What about going in the other direction, smashing vertices together? Is there a name for this?

$\endgroup$
1
$\begingroup$

I would suggest "blowing up the vertex", by analogy to blowing up in algebraic geometry.

$\endgroup$
0
$\begingroup$

If you have an edge $e=\{u,v\}$ in a graph, then the process of "smashing" u and v is called a contraction of the edge e. The result of this contraction is a single vertex $x_{uv}$ which has exactly the same neighbours that $u$ and $v$ had in the original graph.

I don't know if there is a name for the "splitting" process, though.

$\endgroup$
1
  • $\begingroup$ If I had to come up with a name of the process of splitting, I'd call it "fragmentation". I'm posting this as a comment, though, and not as part of the answer, because there might already be an existing name. $\endgroup$
    – Ilefen
    Nov 20 '17 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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