An optimal congestion for embedding the hypercube \(H(n)\) into the line \(P(2^ n)\). (Congestion optimale du plongement de l’hypercube \(H(n)\) dans la chaîne \(P(2^ n)\).) (French) Zbl 0803.68091

Summary: An embedding \(f\) of a guest graph \(G\), into a host graph \(H\), is a one- to-one mapping from each node \(i\) in \(G\) to a unique node \(f(i)\) in \(H\), and from each edge \((i,j)\) in \(G\) to a path in \(H\) starting at node \(f(i)\) and ending at node \(f(j)\). The congestion of \(f\) is the maximum number of times any edge of \(H\) is used by edges of \(G\). The minimum congestion, over all embeddings, is called the congestion of \(G\) into \(H\), and denoted by \(\text{cong}(G,H)\).
In this paper, we consider the problem of optimally embedding the vertices of hypercube graph \(H(n)\), in the vertices of a line \(P(2^ n)\), in order to minimize the congestion; and we show that \[ \text{cong}(H(n),\;P(2^ n))= 1/3\times (2^{n+1}- 2+ (n\text{ modulo }2)). \] Finally, we conjecture that the value of optimal congestion for embedding hypercube \(H(n)\) into cycle \(C(2^ n)\) is \[ \text{cong}(H(n), C(2^ n))= 1/3\times (5\times 2^{n-2}- 2+ (n\text{ modulo }2)). \] {}.


68R10 Graph theory (including graph drawing) in computer science
68M07 Mathematical problems of computer architecture
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI EuDML


[1] 1. S. N. BHATT et F. T. LEIGHTON, A framework for solving VLSI graph layout problems, J. Comput. System Sci., 28, 1984, p. 300-343. Zbl0543.68052 MR760549 · Zbl 0543.68052
[2] 2. P. Z. CHINN, J. CHVÁTALOVÁ, A. K. DEWDNEY et N. E. GIBBS, The bandwidth problem for graphs and matrices-A survey, J. Graph Theory, 6, 1982, p. 223-254. Zbl0494.05057 MR666794 · Zbl 0494.05057
[3] 3. F. R. K. CHUNG, Labelings of graphs, in Selected Topics in Graph Theory, III (L. Beineke and R. Wilson, Eds.), Academic Press, 1988, p. 151-168. Zbl0656.05058 MR1205400 · Zbl 0656.05058
[4] 4. F. R. K. CHUNG et P. D. SEYMOUR, manuscript, Bell Communication Research, Some results on the bandwith and the cutwidth of a graph, 1987.
[5] 5. L. H. HARPER, Optimal assignments of numbers to vertices, J. Soc. Indust. Appl. Math. 9 12, 1964, p. 131-135. Zbl0222.94004 MR162737 · Zbl 0222.94004
[6] 6. L. H. HARPER, Optimal numberings and isoperimetric problems on graphs, J. of Combinatorial Theory, 1, 1966, p. 385-393. Zbl0158.20802 MR200192 · Zbl 0158.20802
[7] 7. J. HROMKOVIC, V. MULLER, O. SYKORA et I. VRTO, On embedding in cycles (to appear). Zbl0826.68012 MR1331730 · Zbl 0826.68012
[8] 8. TEN-HWANG LAI et Alan P. SPRAGUE, Placement of the Processors of a Hypercube, IEEE-Trans.-Comput. 40, 6, 1991, p. 714-722. MR1113977 · Zbl 1395.68016
[9] 9. LEIGHTON, MAGGO, RAO, Universal packet routing algorithms, 29th FOCS, 1988, p. 256-271.
[10] 10. F. MAKEDON, C. H. PAPADIMITRIOU et I. H. SUDBOROUGH, Topological bandwidth, SIAM J. Algebraic Discrete Methods, 6, 1985, p. 418-444. Zbl0573.05052 MR791172 · Zbl 0573.05052
[11] 11. B. MONIEN et I. H. SUDBROUGH, Comparing Interconnection Networks, Proceedings of the 13th Symposium on mathematical Foundations of Computer Science, 1988.
[12] 12. B. MONIEN et I. H. SUDBROUGH, Embedding one Interconnection Network in Another, Computing Suppl., 7, 1990, p. 257-282. Zbl0699.68017 MR1059934 · Zbl 0699.68017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.