We study embeddings of the $n$-dimensional hypercube into the circuit with $2^n$ vertices. We prove that the circular wirelength attains a minimum by gray coding; that was called the CT conjecture by Chavez and Trapp (Discrete Applied Mathematics, 1998). This problem had claimed to be settled by Ching-Jung Guu in her doctoral dissertation "The circular wirelength problem for hypercubes" (University of California, Riverside, 1997). Many argue there are gaps in her proof. We eliminate the gaps in her dissertation.
Qinghui LIU
,
Zhiyi Tang
. A RIGOROUS PROOF ON CIRCULAR WIRELENGTH FOR HYPERCUBES*[J]. Acta mathematica scientia, Series B, 2023
, 43(2)
: 919
-941
.
DOI: 10.1007/s10473-023-0223-3
[1] Arockiaraj M, Shalini A J.Conjectures on wirelength of hypercube into cylinder and torus. Theoretical Computer Science, 2015, 595: 168-171
[2] Bernstein A J.Maximally connected arrays on the n-cube. SIAM J Appl Math, 1967, 15(6): 1485-1489
[3] Bezrukov S L, Chavez J D, Harper L H, et al.Embedding of hypercubes into grids//Brim L, Gruska J, Zlatuska J. Mathematical Foundations of Computer Science. Berlin: Springer, 1998: 693-701
[4] Chavez J D, Trapp R.The cyclic cutwidth of trees. Discrete Applied Mathematics, 1998, 87: 25-32
[5] Erbele J, Chavez J, Trapp R.The Cyclic Cutwidth of Qn. San Bernardino: California State of University, 2003
[6] Guu C J.The Circular Wirelength Problem for Hypercubes [D]. Riverside: University of California River- side, 1997
[7] Guu C J. The Mcfunction. Discrete Mathematics, 2000, 213: 163-167
[8] Harper L H.Optimal assignments of numbers to vertices. J SIAM, 1964, 12(1): 131-135
[9] Harper L H.Global Methods for Isoperimetric Problems. Cambridge: Cambridge University Press, 2004
[10] Manuel P, Rajasingh I, Rajan B, Mercy H.Exact wirelength of hypercube on a grid. Discrete Applied Mathematics, 2009, 157(7): 1486-1495
[11] Takagi T.A simple example of the continuous function without derivative. Proc Phys Math Soc Japan, 1903, 1: 176-177
