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?


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). A related problem of finding an optimal ordering for applying this operation is called Minimum Fill-in.

  • $\begingroup$ 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) $\endgroup$
    – Laakeri
    Dec 19 '20 at 17:26
  • 1
    $\begingroup$ @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. $\endgroup$ Dec 19 '20 at 21: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.