A note on the L(2,1)-labelling problem of G(k, m)

doi:10.1016/j.dam.2022.08.030

	A note on the L(2,1)-labelling problem of G(k, m)
	Ye, Qingjie
刊名	DISCRETE APPLIED MATHEMATICS
	2022-12-15
卷号	322 页码:273-275
关键词	Channel assignment L(21)-labelling
ISSN号	0166-218X
DOI	10.1016/j.dam.2022.08.030
英文摘要	The L(2, 1)-labelling problem is a special case of the channel assignment problem. For a given graph G, a k -L(2, 1)-labelling is defined as a function f : V (G) -> {0, 1, 2, ... , k} such that \|f(u)- f(v)\| > 2 when dG(u, v) = 1 and \|f(u)- f(v)\| > 1 when dG(u, v) = 2. The L(2, 1)-labelling number of G, denoted by lambda(G), is the smallest number k such that G has a k -L(2, 1)-labelling. A graph G E G(k, m) if G is (m + 1)-partite graph with V (G) = V0 u V1 u center dot center dot center dot u Vm, where \|V0\| = \|V1\| = center dot center dot center dot = \|Vm\| = k and the induced subgraph G[Vi u Vj] is a perfect matching for any 0 < i < j < m. Lu and Zhai asked whether lambda(G) = 2m if G E G(k, m) in [An extremal problem on non-full colorable graphs, Discrete Appl. Math. 155 (2007) 2165-2173]. We give a negative answer and prove that for every k > 3 and m > 4, there exists a graph G E G(k, m) with lambda(G) = 2m - 1. (c) 2022 Elsevier B.V. All rights reserved.
资助项目	National Natural Science Foundation of China ; Science and Technology Commission of Shanghai Municipality, China ; [11871222] ; [18dz2271000] ; [19JC1420100]
WOS研究方向	Mathematics
语种	英语
出版者	ELSEVIER
WOS记录号	WOS:000864637600002
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/60886]
专题	中国科学院数学与系统科学研究院
通讯作者	Ye, Qingjie
作者单位	Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Ye, Qingjie. A note on the L(2,1)-labelling problem of G(k, m)[J]. DISCRETE APPLIED MATHEMATICS,2022,322:273-275.
APA	Ye, Qingjie.(2022).A note on the L(2,1)-labelling problem of G(k, m).DISCRETE APPLIED MATHEMATICS,322,273-275.
MLA	Ye, Qingjie."A note on the L(2,1)-labelling problem of G(k, m)".DISCRETE APPLIED MATHEMATICS 322(2022):273-275.