Symmetric routings of the hypercube

✍ Scribed by Jean-Claude König; Dominique Sotteau

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 774 KB
• Volume: 121
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90545-5

✦ Synopsis

In this paper we prove that, for any n and k such that (k-l)C: is even, there exists a set of shortest paths between all the pairs of vertices at distance k of an n-cube such that each vertex is on the same number of paths. We conjecture that there also exists such a set of paths where each edge is on the same number of paths, and we prove it for k odd or k = 2 or 4. If (k -1) Ci is odd, we prove that the numbers of paths going through all vertices (edges) differ of at most by one (two). We then give the same kind of results for paths between all pairs of vertices.