<p>Weighted graphs such that if $x$ and $y$ are nodes in the graph, and $p$ and $p'$ are two paths in the graph between $x$ and $y$, then the weight of $p$ equals the weight of $p'$.</p>

CC BY-SA 3.0
2016-02-04T15:31:17.567Z
If I were to invent a name, I’d call it a [potential](https://en.wikipedia.org/wiki/Scalar_potential) graph.
Emil Jeřábek
CC BY-SA 3.0
2016-02-04T18:58:56.557Z
It's not the same concept, in particular because your question makes sense only for digraphs and these are undirected, but this reminds me a bit of distance-hereditary graphs, graphs in which all induced paths between the same two vertices have the same (unweighted) length.
David Eppstein
CC BY-SA 3.0
2016-02-05T06:55:19.090Z
For undirected graphs, graphs with this property cannot contain cycle. Suppose they do and there's two neighboring vertices $s$ and $t$. Then by the property the edge $e(s,t)$ and the path from $s$ to $t$ that uses the rest of the cycle must have equal weight, say $w$. Now consider the vertex next to t in the cycle, say u and let $w'$ be the weight of the t-u edge. Then the one s-u path has weight w+w' and the other has weight w-w', thus unless w'=0, the property does not hold.
chazisop
CC BY-SA 3.0
2016-02-05T08:22:00.177Z
@chazisop, the *unless* of your contradiction can hold, so really the statement should be that any cycle in an undirected graph with this property must contain only edges of weight 0.
Peter Taylor
CC BY-SA 3.0
2016-02-05T11:22:52.543Z
The statement should be just that the *sum* of edge weights along any cycle is $0$. And if we further state it for undirected cycles, where weights of edges traversed in the wrong direction are negated, then this is *equivalent* to the original condition.
Emil Jeřábek
CC BY-SA 3.0
2016-02-05T11:47:23.397Z
The sum along a cycle being $0$ implies that all weights are $0$ (unless the weights are such that $2=0$): For any edge $l$ on a cycle $C$, we have both $w(l)=w(C\setminus l)$ from OP's condition, and $w(l)=-w(C\setminus l)$ from $w(C)=0$.
Klaus Draeger
CC BY-SA 3.0
2016-02-07T11:32:41.017Z
It seems we are talking past each other. I was considering directed graphs. While the OP somewhat suggests undirected graphs, this makes no sense whatsoever, as the condition then implies all weights are 0 (for any edge e, compare it with the path that traverses e there, back, and there again).
Emil Jeřábek
CC BY-SA 3.0
2016-02-07T11:36:00.117Z
For directed graphs, the condition certainly doesn't imply all edges are 0, even if there are cycles: take e.g. the two-node graph where the edge in one direction has weight 1, and in the opposite direction weight $-1$.
Emil Jeřábek
<graph-theory>
Is there a special name for the following type of graphs?
grapher
# Is there a special name for the following type of graphs?

(Asked by: username_0 on 2016-02-04)

Weighted graphs such that if $x$ and $y$ are nodes in the graph, and $p$ and $p'$ are two paths in the graph between $x$ and $y$, then the weight of $p$ equals the weight of $p'$.

**Tags:** graph-theory

> **Comments:**
> **username_1**: If I were to invent a name, I’d call it a [potential](https://en.wikipedia.org/wiki/Scalar_potential) graph.  
> **username_2**: It's not the same concept, in particular because your question makes sense only for digraphs and these are undirected, but this reminds me a bit of distance-hereditary graphs, graphs in which all induced paths between the same two vertices have the same (unweighted) length.  
> **username_3**: For undirected graphs, graphs with this property cannot contain cycle. Suppose they do and there's two neighboring vertices $s$ and $t$. Then by the property the edge $e(s,t)$ and the path from $s$ to $t$ that uses the rest of the cycle must have equal weight, say $w$. Now consider the vertex next to t in the cycle, say u and let $w'$ be the weight of the t-u edge. Then the one s-u path has weight w+w' and the other has weight w-w', thus unless w'=0, the property does not hold.  
> **username_4**: @username_3, the *unless* of your contradiction can hold, so really the statement should be that any cycle in an undirected graph with this property must contain only edges of weight 0.  
> **username_1**: The statement should be just that the *sum* of edge weights along any cycle is $0$. And if we further state it for undirected cycles, where weights of edges traversed in the wrong direction are negated, then this is *equivalent* to the original condition.  
> **username_5**: The sum along a cycle being $0$ implies that all weights are $0$ (unless the weights are such that $2=0$): For any edge $l$ on a cycle $C$, we have both $w(l)=w(C\setminus l)$ from OP's condition, and $w(l)=-w(C\setminus l)$ from $w(C)=0$.  
> **username_1**: It seems we are talking past each other. I was considering directed graphs. While the OP somewhat suggests undirected graphs, this makes no sense whatsoever, as the condition then implies all weights are 0 (for any edge e, compare it with the path that traverses e there, back, and there again).  
> **username_1**: For directed graphs, the condition certainly doesn't imply all edges are 0, even if there are cycles: take e.g. the two-node graph where the edge in one direction has weight 1, and in the opposite direction weight $-1$.  

---

## 0 answers

