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

<p>Now, I modify <span class="math-container">$G$</span> by adding a copy <span class="math-container">$x'$</span> occurring in the same edges as <span class="math-container">$x$</span> except <span class="math-container">$e$</span> and <span class="math-container">$e_x$</span>, adding a copy <span class="math-container">$y'$</span> occurring in the same edges as <span class="math-container">$y$</span> except <span class="math-container">$e$</span> and <span class="math-container">$e_y$</span>, and replacing the edge <span class="math-container">$e$</span> by two copies <span class="math-container">$\{x, y'\}$</span> and <span class="math-container">$\{x', y\}$</span>.</p>

<p><img src="https://i.sstatic.net/PKa6v.png" alt="Example transformation"></p>

<p><strong>Does this operation have an established name, and is anything known about it?</strong></p>

<p>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., <span class="math-container">$\{a, b\}, \{b, c\}, \{c, d_1\}, \{c, d_2\}$</span>.</p>

CC BY-SA 4.0
2019-04-09T17:57:05.053Z
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.
M.Monet
CC BY-SA 4.0
2019-04-09T18:21:55.060Z
Thanks @M.Monet! So yeah the only remaining question then is whether there is any existing name for this operation.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-06-30T14:17:17.410Z
Could you please share a little bit about your motivation in this graph operation?
Yixin Cao
CC BY-SA 4.0
2019-06-30T15:04:26.537Z
@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.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-08-08T23:08:19.107Z
@YixinCao: Sorry for the delay. The relevant draft is here https://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.
Antoine Amarilli 'a3nm'
<reference-request><graph-theory>
Is there a standard name for this way of modifying graphs?
Antoine Amarilli 'a3nm'
# Is there a standard name for this way of modifying graphs?

(Asked by: username_0 on 2019-03-19)

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](https://i.sstatic.net/PKa6v.png)

**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\}$.

**Tags:** reference-request, graph-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: Thanks @M.Monet! So yeah the only remaining question then is whether there is any existing name for this operation.  
> **username_2**: Could you please share a little bit about your motivation in this graph operation?  
> **username_0**: @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.  
> **username_0**: @YixinCao: Sorry for the delay. The relevant draft is here https://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.  

---

## 0 answers

