Graph Fusion

Topics: Graph Theory

---

(definition)

Let $G$ be a graph with two vertices $v_i$ and $v_j$ connected by an edge $e_k$.

The graph fusion of $G$ relative to $e_k$ (denoted $G/e_k$) is the graph that results from:

1. Removing $e_k$.
2. Adding a new vertex $v_i{v}_j$ that is connected to all the vertices that $v_i$ and $v_j$ were individually connected to.
3. Removing $v_i$ and $v_j$.