Equilibrium Points of Directed Graphs

  • Thread starter Pauly Man
  • Start date
126
0
Suppose I have a directed graph in Rn. Where the graph is a hypercube, (a square in R2, a cube in R3 etc).

Suppose I define an equilibrium point of a directed graph to be a vertex such that I can travel from any adjacent vertex along an edge to that vertex. What is the maximum number of equilibrium points of a directed hypercube in Rn?

As an example in R2:

Code:
*****<*****
*          *  
^          ^
*          *
***** >*****
(For some reason the graph isn't formatting properly, hopefully you can imagine that it is supposed to be a square).

The upper left corner is an equilibrium point for the directed hypercube.

I now wish to work out how to find the maximum number of equilibrium points possible in a directed hypercube in Rn. (Any ideas??)
 
Last edited:
44
1
Unfortunately I could not decipher the plotted graph, but in any case you should consider the proyection of the graph on the plane and then argue, as is usually done in graph theory.
 

damgo

It's pretty straightforward to show that this is the same as the size of the largest set of unconnected vertices. For that, you can consider the construction procedure of "doubling" the n-dimensional hypercube and connecting each original points with its double. Then using induction you find 2^(n-1) for n dimensions.

There's probably a prettier way to do it, but graph theory isn't my thing.
 
126
0
Originally posted by damgo
It's pretty straightforward to show that this is the same as the size of the largest set of unconnected vertices. For that, you can consider the construction procedure of "doubling" the n-dimensional hypercube and connecting each original points with its double. Then using induction you find 2^(n-1) for n dimensions.

There's probably a prettier way to do it, but graph theory isn't my thing.
Thanks damgo. I sat up last night before going to bed and thought about the problem. I came up with this argument (which I'm pleased to see results in the same conclusion you came up with).

There are n2n-1 edges in a hypercube. If we know that we have one equilibrium point then we know the direction of n edges. So it follows that we don't know the direction of n(2n-1-1) edges. If we know of another equilibrium point then we know that it cannot share any edges with the previous equilibrium point, and so we know the direction of another n edges. We therefore do not know the direction of n(2n-1-2) edges.

Continuing on in this fashion we find that for a equilibrium points we have n(2n-1-a) edges for which we are unsure of the direction.

The maximum number of equilibrium points occurs when we know the direction of every edge, which occurs when:

n(2n-1-a) = 0
a = 2n-1
 
126
0
Note that I have edited the graph above, so now it hopefully makes sense).
 

Related Threads for: Equilibrium Points of Directed Graphs

  • Posted
Replies
3
Views
11K
  • Posted
Replies
1
Views
1K
  • Posted
Replies
2
Views
2K
  • Posted
Replies
4
Views
3K
  • Posted
Replies
2
Views
823
  • Posted
Replies
15
Views
2K
  • Posted
Replies
3
Views
5K
Replies
2
Views
886

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top