4
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2020 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$
    – Hermann Gruber
    Dec 19, 2020 at 21:07

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.