<p>Let's assume that we are given two graphs <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes.
<a href="https://i.sstatic.net/ScpH3.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ScpH3.png" alt="enter image description here" /></a></p>
<p><span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> are isomorphic (including matching of the edge weights). However, I would like to check whether they look the same when 'building' them from one edge. i.e. we pick one (not necessarily the same) edge in both graphs and would like to know if they look the same starting from that edge. For the example above, we could choose the edge (1,2) in both graphs and see that they are not the same. If we would choose (1,2) and (5,6), they would be the same.</p>
<p>Are you aware of any algorithm to check this kind of similarity? Or is there even a NetworkX function? For tree graphs I could just use NetworkX's is_isomorphic function. However, my intuition is that this similarity measure should be easier (i.e. faster) to check than isomorphism.</p>
<p>Thanks a lot</p>

CC BY-SA 4.0
2020-07-22T12:53:28.230Z
This question is related: https://cstheory.stackexchange.com/questions/21962/graph-isomorphism-given-a-partial-isomorphism
Denis
CC BY-SA 4.0
2020-07-23T08:27:02.807Z
Can you define precisely what it means to "look the same starting from an edge"? Are you asking whether there is a graph isomorphism that maps that edge in $G_1$ to a particular edge in $G_2$?
D.W.
CC BY-SA 4.0
2020-07-27T13:09:40.013Z
Thanks for your comments! @D.W. That was a bit sloppy - sorry. I think you can think of it as following. Let's assume both graphs have an edge $e=(x,y)$. I would like to check if $G_1$ and $G_2$ are isomorphic with the constraint that the mapping (the isomorphism) maps the edge $e = (x,y)$ of $G_1$ to the same edge $e=(x,y)$ of $G_2$. In the more general case, we could assume - as above - that we have an edge $e_1=(x_1,y_1)$ of $G_1$ and $e_2 = (x_2,y_2)$ of $G_2$ and the constraint that the isomorphism has to map $e_1$ on $e_2$.
Freiburger0
CC BY-SA 4.0
2020-07-27T15:55:32.500Z
OK, please [edit] the question to make that clear, so people don't have to read the comments to understand your question.  You can revise it to read well for someone who encounters it for the first time.
D.W.
<graph-theory><graph-algorithms><graph-isomorphism>
Comparing two graphs when starting from a single edge
Freiburger0
# Comparing two graphs when starting from a single edge

(Asked by: username_0 on 2020-07-22)

Let's assume that we are given two graphs $G\_1$ and $G\_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes.
[![enter image description here](https://i.sstatic.net/ScpH3.png)](https://i.sstatic.net/ScpH3.png)

$G\_1$ and $G\_2$ are isomorphic (including matching of the edge weights). However, I would like to check whether they look the same when 'building' them from one edge. i.e. we pick one (not necessarily the same) edge in both graphs and would like to know if they look the same starting from that edge. For the example above, we could choose the edge (1,2) in both graphs and see that they are not the same. If we would choose (1,2) and (5,6), they would be the same.

Are you aware of any algorithm to check this kind of similarity? Or is there even a NetworkX function? For tree graphs I could just use NetworkX's is\_isomorphic function. However, my intuition is that this similarity measure should be easier (i.e. faster) to check than isomorphism.

Thanks a lot

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

> **Comments:**
> **username_1**: This question is related: https://cstheory.stackexchange.com/questions/21962/graph-isomorphism-given-a-partial-isomorphism  
> **username_2**: Can you define precisely what it means to "look the same starting from an edge"? Are you asking whether there is a graph isomorphism that maps that edge in $G_1$ to a particular edge in $G_2$?  
> **username_0**: Thanks for your comments! @username_2 That was a bit sloppy - sorry. I think you can think of it as following. Let's assume both graphs have an edge $e=(x,y)$. I would like to check if $G_1$ and $G_2$ are isomorphic with the constraint that the mapping (the isomorphism) maps the edge $e = (x,y)$ of $G_1$ to the same edge $e=(x,y)$ of $G_2$. In the more general case, we could assume - as above - that we have an edge $e_1=(x_1,y_1)$ of $G_1$ and $e_2 = (x_2,y_2)$ of $G_2$ and the constraint that the isomorphism has to map $e_1$ on $e_2$.  
> **username_2**: OK, please [edit] the question to make that clear, so people don't have to read the comments to understand your question.  You can revise it to read well for someone who encounters it for the first time.  

---

## 0 answers

