A coloring problem on the n-cube

CSpace

	A coloring problem on the n-cube
	Kim, DS ; Du, DZ ; Pardalos, PM
	2000-07-15
发表期刊	DISCRETE APPLIED MATHEMATICS
ISSN	0166-218X
卷号	103 期号:1-3 页码:307-311
摘要	In this paper, we consider a coloring problem on the n-cube that arises in the study of scalability of optical networks. Let chi((k) over bar)(n) be the minimum number of colors needed to color the vertices of the n-cube so that every two vertices with Hamming distance less than or equal to k have different colors. We show that for k = 3, 2n less than or equal to chi((3) over bar)(n) less than or equal to 2([log2 n]+1). We also provide upper and lower bounds on chi((k) over bar)(n) for general k. (C) 2000 Elsevier Science B.V. All rights reserved.
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000087473600021
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15554
专题	中国科学院数学与系统科学研究院
通讯作者	Du, DZ
作者单位	1.Chinese Acad Sci, Inst Appl Math, Beijing, Peoples R China 2.Univ Minnesota, Dept Comp Sci & Engn, Minneapolis, MN 55455 USA 3.Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA
推荐引用方式 GB/T 7714	Kim, DS,Du, DZ,Pardalos, PM. A coloring problem on the n-cube[J]. DISCRETE APPLIED MATHEMATICS,2000,103(1-3):307-311.
APA	Kim, DS,Du, DZ,&Pardalos, PM.(2000).A coloring problem on the n-cube.DISCRETE APPLIED MATHEMATICS,103(1-3),307-311.
MLA	Kim, DS,et al."A coloring problem on the n-cube".DISCRETE APPLIED MATHEMATICS 103.1-3(2000):307-311.