Simple graph theory terminology question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Bomaz
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC

Simple graph theory terminology question

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
Last edited by Bomaz on Fri Mar 16, 2012 5:50 pm UTC, edited 3 times in total.

gorcee
Posts: 1501
Joined: Sun Jul 13, 2008 3:14 am UTC

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.

Bomaz
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC

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.

Bomaz
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC

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.

jaap
Posts: 2085
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

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.

Tirian
Posts: 1891
Joined: Fri Feb 15, 2008 6:03 pm UTC

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.

Bomaz
Posts: 22
Joined: Wed Dec 26, 2007 7:06 pm UTC

Re: Simple graph theory terminology question

Ok, thanks for the help people