<p>This operation is called vertex elimination. See for example: &quot;Triangulated Graphs and the Elimination Process&quot;, by Rose (1970).</p>
<p>This type of operation is well-studied, among others, in the context of chordal graphs (see <a href="https://en.wikipedia.org/wiki/Chordal_graph#Perfect_elimination_and_efficient_recognition" rel="noreferrer">Wikipedia entry about perfect elimination orderings</a>). A related problem of finding an optimal ordering for applying this operation is called Minimum Fill-in.</p>

CC BY-SA 4.0
2020-12-19T17:26:34.520Z
It seems that the asker is talking about directed graphs. Do these concepts apply also for them? (Though the asker seems happy with the answer)
Laakeri
CC BY-SA 4.0
2020-12-19T21:07:15.773Z
@Laakeri yes. In the context of conversion of finite automata to regular expressions, this is nothing else than "state elimination". Using methods from (di)graph theory it is possible to give nontrivial bounds on regular expression size if we choose the "right" elimination ordering.
Hermann Gruber
CC BY-SA 4.0
2020-12-19T15:49:26.970Z
2020-12-19T15:49:26.970Z
Michael Lampis
<p>I have an operation that looks a lot like vertex removal, and I'm wondering if there's a standard name for it. Given a graph <span class="math-container">$G$</span> we remove a vertex <span class="math-container">$v$</span>, but instead of removing the edges that were incident on <span class="math-container">$v$</span>, we &quot;re-route&quot; them by connecting all incoming and outgoing edge pairs. Specifically, if <span class="math-container">$-$</span> is normal vertex deletion and we're trying to define <span class="math-container">$\ominus$</span>, then</p>
<p><span class="math-container">$$G \ominus v \equiv G - v + \{ uw | uv \in G \land vw \in G\}.$$</span></p>
<p>Is there any standard name for this operation?</p>

<graph-theory>
Standard Name for a vertex removal like operation
Ben Jones
# Standard Name for a vertex removal like operation

(Asked by: username_0 on 2020-12-19)

I have an operation that looks a lot like vertex removal, and I'm wondering if there's a standard name for it. Given a graph $G$ we remove a vertex $v$, but instead of removing the edges that were incident on $v$, we "re-route" them by connecting all incoming and outgoing edge pairs. Specifically, if $-$ is normal vertex deletion and we're trying to define $\ominus$, then

$$G \ominus v \equiv G - v + \{ uw | uv \in G \land vw \in G\}.$$

Is there any standard name for this operation?

**Tags:** graph-theory


---

## 1 answers

### Answer by username_1 on 2020-12-19. Score: 5 | Accepted answer

This operation is called vertex elimination. See for example: "Triangulated Graphs and the Elimination Process", by Rose (1970).

This type of operation is well-studied, among others, in the context of chordal graphs (see [Wikipedia entry about perfect elimination orderings](https://en.wikipedia.org/wiki/Chordal_graph#Perfect_elimination_and_efficient_recognition)). A related problem of finding an optimal ordering for applying this operation is called Minimum Fill-in.

> **Comments:**
> **username_2**: It seems that the asker is talking about directed graphs. Do these concepts apply also for them? (Though the asker seems happy with the answer)  
> **username_3**: @username_2 yes. In the context of conversion of finite automata to regular expressions, this is nothing else than "state elimination". Using methods from (di)graph theory it is possible to give nontrivial bounds on regular expression size if we choose the "right" elimination ordering.  

---

