What is a directed graph called if it has the property that all simple paths from some node n1 to a node n2 have the same length? (in this case length is defined as weights given to each edge in the usual manner of the shortest path problem)

Edit: added the requirement of the graph being simple

## Simple graph theory terminology question

**Moderators:** gmalivuk, Moderators General, Prelates

### Simple graph theory terminology question

Last edited by Bomaz on Fri Mar 16, 2012 5:50 pm UTC, edited 3 times in total.

### Re: Simple graph theory terminology question

I'm a little uncertain what you mean by length. Do you mean length in terms of graph distance, which is a measure of the number of "steps" it takes to get from one point to another? (ie, from A to B to D would be distance 2). In such a case, the properties you're talking about would require the graph to be totally connected (every node is 1 step away from every other node).

Typically, we don't really care about the location of the nodes in some externally-fixed coordinate system, so, for instance, a Euclidean metric doesn't really mean much. We can get around that by assigning a weight to each connection, and link that weight to the physical separation between nodes w/r.t. some external metric. If this is what you're doing, you could just call the graph uniformly weighted.

These aren't really terms, per se, but rather a combination of phrases that have more or less universal meaning.

Typically, we don't really care about the location of the nodes in some externally-fixed coordinate system, so, for instance, a Euclidean metric doesn't really mean much. We can get around that by assigning a weight to each connection, and link that weight to the physical separation between nodes w/r.t. some external metric. If this is what you're doing, you could just call the graph uniformly weighted.

These aren't really terms, per se, but rather a combination of phrases that have more or less universal meaning.

### Re: Simple graph theory terminology question

With length I mean that with each edge having a given distance. the length of a path is the sum of the edges contained in the path. As per the normal definition of the shortest path problem

Last edited by Bomaz on Fri Mar 16, 2012 5:16 pm UTC, edited 1 time in total.

- Talith
- Proved the Goldbach Conjecture
**Posts:**848**Joined:**Sat Nov 29, 2008 1:28 am UTC**Location:**Manchester - UK

### Re: Simple graph theory terminology question

Surely if p is a path from n1 to n2, then q=p(-p)p is a path from n1 to n2 also, but this path is 3 times as long as p, so no such graph exists.

### Re: Simple graph theory terminology question

Ah, I am sorry I should have stated it as a simple path. I will now edit my original post to reflect this.

### Re: Simple graph theory terminology question

Talith wrote:Surely if p is a path from n1 to n2, then q=p(-p)p is a path from n1 to n2 also, but this path is 3 times as long as p, so no such graph exists.

But this is a directed graph, so unless all those edges that form p are bidirectional, your construction does not work.

You don't want the graph to have any loops (of length k!=0) in it though, because if there is a loop going through the node n, then the distance from n to n is 0 or k.

I don't know if this property has a name.

### Re: Simple graph theory terminology question

jaap wrote:I don't know if this property has a name.

Agreed. Graph theory is notorious for esoteric vocabulary, but you'd be on safe ground just clearly defining this as (n1-n2)-isopathitude or Property P or whatever in your introduction if you want to refer to it several times.

- Proginoskes
**Posts:**313**Joined:**Mon Nov 14, 2011 7:07 am UTC**Location:**Sitting Down

### Re: Simple graph theory terminology question

The closest term to what the OP wants, that I have heard of, is a geodesic; his directed graph has the property that every simple (u,v)-path is a geodesic.

### Re: Simple graph theory terminology question

Ok, thanks for the help people

### Who is online

Users browsing this forum: Spike and 3 guests