Page 1 of 1

Simple graph theory terminology question

Posted: Fri Mar 16, 2012 1:31 pm UTC
by Bomaz
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

Re: Simple graph theory terminology question

Posted: Fri Mar 16, 2012 4:48 pm UTC
by gorcee
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.

Re: Simple graph theory terminology question

Posted: Fri Mar 16, 2012 4:55 pm UTC
by Bomaz
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

Re: Simple graph theory terminology question

Posted: Fri Mar 16, 2012 4:56 pm UTC
by Talith
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

Posted: Fri Mar 16, 2012 5:47 pm UTC
by Bomaz
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

Posted: Fri Mar 16, 2012 6:15 pm UTC
by jaap
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

Posted: Fri Mar 16, 2012 6:29 pm UTC
by Tirian
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.

Re: Simple graph theory terminology question

Posted: Sat Mar 17, 2012 7:52 am UTC
by Proginoskes
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

Posted: Sat Mar 17, 2012 11:44 am UTC
by Bomaz
Ok, thanks for the help people