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 '19 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 '19 at 18:21
  • $\begingroup$ Could you please share a little bit about your motivation in this graph operation? $\endgroup$ – Yixin Cao Jun 30 '19 at 14:17
  • $\begingroup$ @YixinCao: It's about having a sequence of homomorphic graphs to find some that are minimal in some sense, for a dichotomy result on some counting problems. We're busy writing it up but I'll post back with a link to an online draft once it's ready. $\endgroup$ – a3nm Jun 30 '19 at 15:04
  • $\begingroup$ @YixinCao: Sorry for the delay. The relevant draft is here a3nm.net/publications/amarilli2019dichotomy.pdf. The specific operation I asked about no longer appears in it, but some of its cousins do (fine dissociation and iteration). I'd be interested in names for such operations (or variants) if some exist. $\endgroup$ – a3nm Aug 8 '19 at 23:08

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.