<p>First of all, thank you Command Master for the website! And credits to the creator of
<a href="https://funkybee.narod.ru/graphs.htm" rel="nofollow noreferrer">https://funkybee.narod.ru/graphs.htm</a>. (I did not see a profile page for the creator, but I would be happy to put a link if someone can find that). After looking at Pair #30 (immediately visible on the website), I came up with a counter-example to resolve Questions 1 and 3.</p>
<p>Question 1: <strong>no.</strong> See the counterexample in Question 3. Note, however, that this equation <strong>does</strong> uniquely determine the edge map. In other words, to construct a support translation <span class="math-container">$\rho,$</span> we only need a map <span class="math-container">$\rho_V$</span> between vertices.</p>
<p>Question 2: <strong>yes.</strong> This follows from a simple calculation with composites:</p>
<ol>
<li>Left compose both sides by <span class="math-container">$\rho^{-1}_E.$</span></li>
<li>Right compose both sides by <span class="math-container">$\rho^{-1}_V.$</span></li>
</ol>
<p>Question 3: <strong>in general, support translations do not preserve vertex adjacency.</strong> The premise need not be true.</p>
<p>The first counterexample I found is Pair #30, containing two non-isomorphic graphs. Two important points here:</p>
<ul>
<li>Colors represent points that <em>can</em> be mapped to one another. Only the pink and blue points are degree 2; all other points are degree 3. My construction preserves these colors, though this is not strictly necessary. We can interpret the colors as controls, but it is easy to apply restriction 4 and find the same results.</li>
<li>Ports <strong>are</strong> invariant under support translation, so it doesn’t matter how we place them. Grezlak and Aßmann don’t explicitly include ports in their examples and algorithm. I am not sure exactly what purpose explicit ports serve, but the algorithm works either way.</li>
</ul>
<p><a href="https://i.sstatic.net/bALzV.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bALzV.jpg" alt="Pair 30" /></a></p>
<p>This graph is a bit too large to check an explicit mapping. But we can easily fix this by removing the paths at the bottom of each graph, keeping only the pink and green points. Here’s the resulting link graphs, with labels as a visual aid. (Most of the labels match with their color names, except for blue). Again, note that we could replace each other by vertex degree without changing the main results.</p>
<p><a href="https://i.sstatic.net/Ix4ma.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Ix4ma.png" alt="enter image description here" /></a></p>
<p><strong>[Edit 1 (March 16, 2024):</strong> My original solution contains a small mistake. I checked my counterexample with the python module <a href="https://python.igraph.org/en/stable/" rel="nofollow noreferrer">igraph</a>, and apparently, my original example is an isomorphic pair of graphs. However, I noticed I excluded something from Pair 30: a vertex <span class="math-container">$s$</span> that only connects to <span class="math-container">$a_1.$</span> By adding this in, igraph confirms that this <em>is</em> a valid example. In fact, these pair are not <em>subgraph isomorphic,</em> so it’s impossible to find a bijective graph homomorphism between this pair. This means bigraph isomorphism doesn’t preserve edge adjacency, which completely resolves Question 1. I will recreate my diagrams in a new edit, probably using pyplot.</p>
<p>My justification requires two small changes:</p>
<ul>
<li><span class="math-container">$s$</span> is sent to itself in the support translation, and</li>
<li>Label the edge from <span class="math-container">$s$</span> to <span class="math-container">$a_1$</span> with <span class="math-container">$0.$</span> This will change the starting edge in our enumerations, but that’s it.
<strong>]</strong></li>
</ul>
<p>For the same reason as Pair #30 (there are “crossing” edges <span class="math-container">$(r_1, p_2), (r_2, p_1)$</span> in <span class="math-container">$G$</span> but not in <span class="math-container">$F$</span>), <span class="math-container">$F, G$</span> are not graph isomorphic.</p>
<p>Now it is easier to construct a support translation. By the answer to Question 1, we primarily need the vertex map
<span class="math-container">$\rho_V: F \to G.$</span></p>
<ul>
<li><p>Send <span class="math-container">$r_1 \in F$</span> to <span class="math-container">$r_2 \in G,$</span></p>
</li>
<li><p>Send <span class="math-container">$r_2 \in F$</span> to <span class="math-container">$r_1 \in G,$</span></p>
</li>
<li><p>Send <span class="math-container">$b_{2i} \in F$</span> to <span class="math-container">$b_{2i-1} \in G $</span> <span class="math-container">$(i = 1, 2),$</span></p>
</li>
<li><p>Send <span class="math-container">$b_{2i-1} \in F$</span> to <span class="math-container">$b_{2i} \in G,$</span></p>
</li>
<li><p>Send <span class="math-container">$a_1 \in F$</span> to <span class="math-container">$a_2 \in G,$</span></p>
</li>
<li><p>Send <span class="math-container">$a_2 \in F$</span> to <span class="math-container">$a_1 \in G,$</span></p>
</li>
<li><p>Send everything else to itself.</p>
</li>
</ul>
<p>In other words, <span class="math-container">$\rho_V$</span> is a permutation that switches the pair of red points, the pair of blue points, <span class="math-container">$b_1$</span> and <span class="math-container">$b_2$</span>, and <span class="math-container">$b_3$</span> and <span class="math-container">$b_4$</span>, fixing everything else.</p>
<p>We know that the edge map is uniquely determined, but here’s the important part: we need to preserve and reflect <em>edge enumerations.</em> That was my recent realization with Grezlak and Aßmann’s algorithm: the canonical string (via my restrictions) <em>exactly</em> preserves degree sequences and this enumeration. By construction, the degree sequences are the same, and all we need to do is show this property: edges preserve vertex degrees. We don’t need edges to be identical, as we are allowed to permute the vertices to find a map. Numbers 1-8 in <span class="math-container">$F$</span> below are arbitrary, but they do mark the edges from degree 2 vertices first. Then the remaining edges are marked. The picture in <span class="math-container">$G$</span> is similar. As expected, <span class="math-container">$\rho_E$</span> permutes the edges based on <span class="math-container">$\rho_V.$</span></p>
<p><a href="https://i.sstatic.net/RXIGx.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/RXIGx.jpg" alt="enter image description here" /></a></p>
<p>To emphasize, in bigraphs with restriction 4, vertices of the same degree may be chosen in a random order. This doesn’t change the underlying edges, which is are my main focus.</p>
<p>I don’t know whether this is the smallest example, but I do know how to construct larger ones. This includes Pair #30, but we can go farther: in the smaller example, extend each blue point in <span class="math-container">$F, G,$</span> respectively, by the same number of edges in a single path. The resulting pair will still be non-isomorphic <em>as graphs</em>, but the above permutation shows they must be bigraph isomorphic. We can make more complicated graphs from the blue points, as long as they are bigraph isomorphic. This extension is worth noting: there are infinitely many <strong>structurally distinct</strong> counterexamples. If only one counterexample existed, it would be fairly easy to check in a graph isomorphism algorithm, but this is not the case.</p>

CC BY-SA 4.0
2024-03-14T21:36:20.483Z
2024-03-18T23:04:56.520Z
2024-03-18T23:04:56.520Z
Oscar Bender-Stone
<p>I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: <a href="https://link.springer.com/content/pdf/10.1007/s42979-021-00552-5.pdf" rel="nofollow noreferrer">“A Canonical
String Encoding for Pure Bigraphs.”</a> On page 2, they define the notion of a bigraph, which is roughly a forest and hypergraph on a common set of vertices. (The terminology comes from Robin Milner and does not directly connect to bipartile graphs). Here is a more detailed definition for reference (page 16, <a href="https://www.cl.cam.ac.uk/archive/rm135/Bigraphs-draft.pdf#page=17" rel="nofollow noreferrer">Milner</a>). Note that the set of controls <span class="math-container">$\mathcal{K}$</span> is equipped with an arity map <span class="math-container">$ar: \mathcal{K} \to \mathbb{N}.$</span></p>
<p><a href="https://i.sstatic.net/rEWR5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rEWR5.png" alt="enter image description here" /></a></p>
<p>Grezlak and Aßmann provide a polynomial time algorithm for bigraph isomorphism. This notion of isomorphism is a support translation, given in Definition 2.4, page 17 of <a href="https://www.cl.cam.ac.uk/archive/rm135/Bigraphs-draft.pdf#page=17" rel="nofollow noreferrer">Robin Milner’s “The Space and Motion of Communicating Agents.”</a></p>
<p><a href="https://i.sstatic.net/wDAsg.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/wDAsg.png" alt="enter image description here" /></a></p>
<p>I am trying to determine whether graph isomorphism reduces to bigraph isomorphism. I want to find a counter example, because graph isomorphism is a hard problem and is not known to be in <span class="math-container">$P.$</span> I understand that the definition of suppport equivalence preserves the order of two new structures: the controls and ports. However, I want to consider a case where both of these are fixed. More specifically, I am considering five restrictions:</p>
<ol>
<li>The forest is a shallow tree: there is a root that is the parent of all other nodes.</li>
<li>The hypergraph is a simple graph (each edge corresponds to exactly two vertices),</li>
<li>The sets of inner and outer names are empty,</li>
<li><span class="math-container">$ar$</span> is injective, and</li>
<li>Order the ports as follows: for any vertex <span class="math-container">$v,$</span> rank adjacent vertices based on their degree. Port 1 of <span class="math-container">$v$</span> is connected to the vertex with least degree, port 2 is connected to the vertex with 2nd least degree, etc. (If there is a tie, choose one of them first randomly).</li>
</ol>
<p>Fix bigraphs <span class="math-container">$F, G$</span> with restrictions 1-5, and suppose there is a support translation <span class="math-container">$\rho: F \to G.$</span> Here are my main questions:</p>
<ol>
<li>If the link function is preserved, does that mean that <span class="math-container">$\rho$</span> preserves vertex adjacency (like in a graph homomorphism)?</li>
<li>Is the link function reflected? In other words, is it true that
<span class="math-container">$\rho_E^{-1} \circ link_G = link_F \circ \rho_{P}^{-1}$</span>? (Note that I am abusing notation here; I am ignoring both <span class="math-container">$X, Y$</span>, as they are both empty).</li>
<li>If 1 and 2 are true, does this mean that the corresponding function between the link graphs of <span class="math-container">$F, G,$</span> respectively, is a graph isomorphism?</li>
</ol>
<p>My current approach involves finding examples of non-isomorphic graphs online, from which I can then construct into bigraphs. As far as I can tell, <a href="https://www.graphclasses.org/smallgraphs.html" rel="nofollow noreferrer">graphs with size 4 and below</a> are not that helpful. In these cases, it appears that each isomorphism class has exactly one element (i.e., is uniquely determined by degree sequence). I need an example where two non-isomorphic graphs have the same degree sequence and, preferably, are both small. So far, the examples that I have tried do not work; I can post them, if requested.</p>
<p>Please let me know if this question is more appropriate on a different SE site. I am happy to look into any suggested reference; I have not been able to find discussions related to these questions in the literature.</p>
<p>Edit 1: I figured out that a bigraph isomorphism not only preserves degree sequences, but also edge enumerations. Here’s my basic reasoning: Grezlak and Aßmann’s main algorithm does a BFS traversal on the place graph and, simultaneously, numbers each edge that hasn’t yet been traversed. This encodes both the place and link graphs. (I am ignoring inner and outer names here, but the procedure is similar). Based on my restrictions, this means there will only be two phases of BFS: marking the root node, and the traversal through the root’s children. This creates a unique string, the canonical encoding of the bigraph. Two bigraphs are isomorphic if they produce the same encoding. From my experiments, maintaining this edge enumeration appears to preserve cycles, so in a counterexample, I except both link graphs need to have an equal number of cycles (of the same length).</p>

CC BY-SA 4.0
2024-03-09T05:30:17.363Z
You can try to take a look at the pairs in https://funkybee.narod.ru/graphs.htm
Command Master
CC BY-SA 4.0
2024-03-12T21:51:04.483Z
Thank you! I need to investigate the first graph that appeared on the link; I suspect a counterexample will have some sort of “crossing” edge behavior. (My intuition says two isomorphic bigraphs could differ by a pair of “crossing” edges, visually, but they wouldn’t be graph isomorphic).
Oscar Bender-Stone
<graph-theory><graph-isomorphism>
Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?
Oscar Bender-Stone
# Is (Restricted) Bigraph Isomorphism Weaker than Graph Isomorphism?

(Asked by: username_0 on 2024-03-08)

I am investigating a paper from Dominik Grezlak and and Uwe Aßmann: [“A Canonical
String Encoding for Pure Bigraphs.”](https://link.springer.com/content/pdf/10.1007/s42979-021-00552-5.pdf) On page 2, they define the notion of a bigraph, which is roughly a forest and hypergraph on a common set of vertices. (The terminology comes from Robin Milner and does not directly connect to bipartile graphs). Here is a more detailed definition for reference (page 16, [Milner](https://www.cl.cam.ac.uk/archive/rm135/Bigraphs-draft.pdf#page=17)). Note that the set of controls $\mathcal{K}$ is equipped with an arity map $ar: \mathcal{K} \to \mathbb{N}.$

[![enter image description here](https://i.sstatic.net/rEWR5.png)](https://i.sstatic.net/rEWR5.png)

Grezlak and Aßmann provide a polynomial time algorithm for bigraph isomorphism. This notion of isomorphism is a support translation, given in Definition 2.4, page 17 of [Robin Milner’s “The Space and Motion of Communicating Agents.”](https://www.cl.cam.ac.uk/archive/rm135/Bigraphs-draft.pdf#page=17)

[![enter image description here](https://i.sstatic.net/wDAsg.png)](https://i.sstatic.net/wDAsg.png)

I am trying to determine whether graph isomorphism reduces to bigraph isomorphism. I want to find a counter example, because graph isomorphism is a hard problem and is not known to be in $P.$ I understand that the definition of suppport equivalence preserves the order of two new structures: the controls and ports. However, I want to consider a case where both of these are fixed. More specifically, I am considering five restrictions:

1. The forest is a shallow tree: there is a root that is the parent of all other nodes.
2. The hypergraph is a simple graph (each edge corresponds to exactly two vertices),
3. The sets of inner and outer names are empty,
4. $ar$ is injective, and
5. Order the ports as follows: for any vertex $v,$ rank adjacent vertices based on their degree. Port 1 of $v$ is connected to the vertex with least degree, port 2 is connected to the vertex with 2nd least degree, etc. (If there is a tie, choose one of them first randomly).

Fix bigraphs $F, G$ with restrictions 1-5, and suppose there is a support translation $\rho: F \to G.$ Here are my main questions:

1. If the link function is preserved, does that mean that $\rho$ preserves vertex adjacency (like in a graph homomorphism)?
2. Is the link function reflected? In other words, is it true that
   $\rho\_E^{-1} \circ link\_G = link\_F \circ \rho\_{P}^{-1}$? (Note that I am abusing notation here; I am ignoring both $X, Y$, as they are both empty).
3. If 1 and 2 are true, does this mean that the corresponding function between the link graphs of $F, G,$ respectively, is a graph isomorphism?

My current approach involves finding examples of non-isomorphic graphs online, from which I can then construct into bigraphs. As far as I can tell, [graphs with size 4 and below](https://www.graphclasses.org/smallgraphs.html) are not that helpful. In these cases, it appears that each isomorphism class has exactly one element (i.e., is uniquely determined by degree sequence). I need an example where two non-isomorphic graphs have the same degree sequence and, preferably, are both small. So far, the examples that I have tried do not work; I can post them, if requested.

Please let me know if this question is more appropriate on a different SE site. I am happy to look into any suggested reference; I have not been able to find discussions related to these questions in the literature.

Edit 1: I figured out that a bigraph isomorphism not only preserves degree sequences, but also edge enumerations. Here’s my basic reasoning: Grezlak and Aßmann’s main algorithm does a BFS traversal on the place graph and, simultaneously, numbers each edge that hasn’t yet been traversed. This encodes both the place and link graphs. (I am ignoring inner and outer names here, but the procedure is similar). Based on my restrictions, this means there will only be two phases of BFS: marking the root node, and the traversal through the root’s children. This creates a unique string, the canonical encoding of the bigraph. Two bigraphs are isomorphic if they produce the same encoding. From my experiments, maintaining this edge enumeration appears to preserve cycles, so in a counterexample, I except both link graphs need to have an equal number of cycles (of the same length).

**Tags:** graph-theory, graph-isomorphism

> **Comments:**
> **username_1**: You can try to take a look at the pairs in https://funkybee.narod.ru/graphs.htm  
> **username_0**: Thank you! I need to investigate the first graph that appeared on the link; I suspect a counterexample will have some sort of “crossing” edge behavior. (My intuition says two isomorphic bigraphs could differ by a pair of “crossing” edges, visually, but they wouldn’t be graph isomorphic).  

---

## 1 answers

### Answer by username_0 on 2024-03-14. Score: 0 | Accepted answer

First of all, thank you username_1 for the website! And credits to the creator of
<https://funkybee.narod.ru/graphs.htm>. (I did not see a profile page for the creator, but I would be happy to put a link if someone can find that). After looking at Pair #30 (immediately visible on the website), I came up with a counter-example to resolve Questions 1 and 3.

Question 1: **no.** See the counterexample in Question 3. Note, however, that this equation **does** uniquely determine the edge map. In other words, to construct a support translation $\rho,$ we only need a map $\rho\_V$ between vertices.

Question 2: **yes.** This follows from a simple calculation with composites:

1. Left compose both sides by $\rho^{-1}\_E.$
2. Right compose both sides by $\rho^{-1}\_V.$

Question 3: **in general, support translations do not preserve vertex adjacency.** The premise need not be true.

The first counterexample I found is Pair #30, containing two non-isomorphic graphs. Two important points here:

* Colors represent points that *can* be mapped to one another. Only the pink and blue points are degree 2; all other points are degree 3. My construction preserves these colors, though this is not strictly necessary. We can interpret the colors as controls, but it is easy to apply restriction 4 and find the same results.
* Ports **are** invariant under support translation, so it doesn’t matter how we place them. Grezlak and Aßmann don’t explicitly include ports in their examples and algorithm. I am not sure exactly what purpose explicit ports serve, but the algorithm works either way.

[![Pair 30](https://i.sstatic.net/bALzV.jpg)](https://i.sstatic.net/bALzV.jpg)

This graph is a bit too large to check an explicit mapping. But we can easily fix this by removing the paths at the bottom of each graph, keeping only the pink and green points. Here’s the resulting link graphs, with labels as a visual aid. (Most of the labels match with their color names, except for blue). Again, note that we could replace each other by vertex degree without changing the main results.

[![enter image description here](https://i.sstatic.net/Ix4ma.png)](https://i.sstatic.net/Ix4ma.png)

**[Edit 1 (March 16, 2024):** My original solution contains a small mistake. I checked my counterexample with the python module [igraph](https://python.igraph.org/en/stable/), and apparently, my original example is an isomorphic pair of graphs. However, I noticed I excluded something from Pair 30: a vertex $s$ that only connects to $a\_1.$ By adding this in, igraph confirms that this *is* a valid example. In fact, these pair are not *subgraph isomorphic,* so it’s impossible to find a bijective graph homomorphism between this pair. This means bigraph isomorphism doesn’t preserve edge adjacency, which completely resolves Question 1. I will recreate my diagrams in a new edit, probably using pyplot.

My justification requires two small changes:

* $s$ is sent to itself in the support translation, and
* Label the edge from $s$ to $a\_1$ with $0.$ This will change the starting edge in our enumerations, but that’s it.
  **]**

For the same reason as Pair #30 (there are “crossing” edges $(r\_1, p\_2), (r\_2, p\_1)$ in $G$ but not in $F$), $F, G$ are not graph isomorphic.

Now it is easier to construct a support translation. By the answer to Question 1, we primarily need the vertex map
$\rho\_V: F \to G.$

* Send $r\_1 \in F$ to $r\_2 \in G,$
* Send $r\_2 \in F$ to $r\_1 \in G,$
* Send $b\_{2i} \in F$ to $b\_{2i-1} \in G $ $(i = 1, 2),$
* Send $b\_{2i-1} \in F$ to $b\_{2i} \in G,$
* Send $a\_1 \in F$ to $a\_2 \in G,$
* Send $a\_2 \in F$ to $a\_1 \in G,$
* Send everything else to itself.

In other words, $\rho\_V$ is a permutation that switches the pair of red points, the pair of blue points, $b\_1$ and $b\_2$, and $b\_3$ and $b\_4$, fixing everything else.

We know that the edge map is uniquely determined, but here’s the important part: we need to preserve and reflect *edge enumerations.* That was my recent realization with Grezlak and Aßmann’s algorithm: the canonical string (via my restrictions) *exactly* preserves degree sequences and this enumeration. By construction, the degree sequences are the same, and all we need to do is show this property: edges preserve vertex degrees. We don’t need edges to be identical, as we are allowed to permute the vertices to find a map. Numbers 1-8 in $F$ below are arbitrary, but they do mark the edges from degree 2 vertices first. Then the remaining edges are marked. The picture in $G$ is similar. As expected, $\rho\_E$ permutes the edges based on $\rho\_V.$

[![enter image description here](https://i.sstatic.net/RXIGx.jpg)](https://i.sstatic.net/RXIGx.jpg)

To emphasize, in bigraphs with restriction 4, vertices of the same degree may be chosen in a random order. This doesn’t change the underlying edges, which is are my main focus.

I don’t know whether this is the smallest example, but I do know how to construct larger ones. This includes Pair #30, but we can go farther: in the smaller example, extend each blue point in $F, G,$ respectively, by the same number of edges in a single path. The resulting pair will still be non-isomorphic *as graphs*, but the above permutation shows they must be bigraph isomorphic. We can make more complicated graphs from the blue points, as long as they are bigraph isomorphic. This extension is worth noting: there are infinitely many **structurally distinct** counterexamples. If only one counterexample existed, it would be fairly easy to check in a graph isomorphism algorithm, but this is not the case.


---

