A RIGOROUS PROOF ON CIRCULAR WIRELENGTH FOR HYPERCUBES  

作　　者：刘庆晖 唐志毅 Qinghui LIU;Zhiyi TANG(School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China)

机构地区：[1]School of Computer Science and Technology,Beijing Institute of Technology,Beijing 100081,China

出　　处：《Acta Mathematica Scientia》2023年第2期919-941,共23页数学物理学报（B辑英文版）

基　　金：supported by the NSFC(11871098)。

摘　　要：We study embeddings of the n-dimensional hypercube into the circuit with 2nvertices.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.

关 键 词：circular wirelength HYPERCUBE gray coding 

分 类 号：O157.5[理学—数学]