Let $G = (V, E)$ be an undirected graph. Let me take an edge $\{x, y\}$ (in blue in the drawing) such that $x$ and $y$ have other incident edges. Among the incident edges we choose one edge $e_x = \{u_1, x\}$ for $x$ and one edge $e_y = \{y, v_m\}$ for $y$ (in red in the drawing).

Now, I modify $G$ by adding a copy $x'$ occurring in the same edges as $x$ except $e$ and $e_x$, adding a copy $y'$ occurring in the same edges as $y$ except $e$ and $e_y$, and replacing the edge $e$ by two copies $\{x, y'\}$ and $\{x', y\}$.

Example transformation

Does this operation have an established name, and is anything known about it?

One question for instance is to understand for which graphs there is a sequence of such operations that will terminate (the operation is no longer applicable to any edge, i.e., each edge has one vertex which is a leaf, or equivalently the graph is a union of stars), for which graph all sequences terminate, and is there confluence (do all terminating sequences on an input graph give the same result up to isomorphism). There are fairly simple graphs where applying sequences of this operation will never terminate, e.g., $\{a, b\}, \{b, c\}, \{c, d_1\}, \{c, d_2\}$.

  • 2
    $\begingroup$ If a graph $G$ contains the pattern $P$ that you mention ($\{a,b\}$, $\{b,c\}$,$\{c,d_1\}$,$\{c,d_2\}$) then no sequence of such operations can terminate, since we can never get rid of $P$. If $G$ does not contain $P$ then $G$ must be a disjoint union of stars, paths, and cycles, and then any sequence of such operation will terminate, and they all converge on the same graph. $\endgroup$ – M.Monet Apr 9 at 17:57
  • $\begingroup$ Thanks @M.Monet! So yeah the only remaining question then is whether there is any existing name for this operation. $\endgroup$ – a3nm Apr 9 at 18:21

Your Answer

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

Browse other questions tagged or ask your own question.