[News]

News: Welcome to The Oktave Forum.

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

The powers of graphs are interesting structures. The p^th power, G^p of a graph G is obtained by adding edges between nodes in G that are separated by a pathlength (greater than 1 and) less than or equal to p. Specifically, the square of a graph is the graph resulting from joining all nodes that are separated by a pathlength 2. A cube of a graph is obtained by short-circuiting all 2 length and 3 length paths in the graph.

An important consequence of raising the graph to a power is diameter reduction. If G has diameter d, then graph G^p has diameter \ceil{d/p}. There are several other interesting properties of graph powers that we can observe. (Several of them are important to the design of optimal graph topologies.) I’d be interested in knowing your ideas.

---

Cross posted on my blog http://1stprinciples.wordpress.com/.

[sri]

sri

sri

Show sri's last posts.

Show general stats for sri.

• 
• Administrator
• Sr. Member
• Karma: 7
• Posts: 264

I would like to propose a set of simpler operations out of which graph powers can be created. The first is a "k-bridge", where you add edges between pairs of nodes in a graph that are separated (exactly) by length k. The second is "graph union" where G₁ U G₂ is defined iff both graphs have the same set of vertices. The union is simply the set of all edges from both the graphs.

You can now see how we can build a graph power p from k-bridges and unions. Just take all k-bridges for k = 2..p and compute the union for all the graphs.

Why I bring this up is that k-bridges over hamiltonian circuits (or 2-regular graphs) have some interesting properties. The post on Sieve puzzle addresses some of these properties..

[sanket]

sanket

sanket

Show sanket's last posts.

Show general stats for sanket.

• 
• Global Moderator
• Full Member
• Karma: 4
• Posts: 104

Yes. Actually, I am interested in understanding what happens when we short-circuit nodes that are separated by a distance of exactly k. In fact, our first approach to diameter optimization of topologies was this. To add edges between nodes that are ends of diameters.