On the Computational Complexity of the L(2, 1)-Labeling Problem for Regular Graphs
On the Computational Complexity of the L(2, 1)-Labeling Problem for Regular Graphs
复制标题
正则图的 L(2, 1) 标记问题的计算复杂度
DOI：
10.1007/11560586_19
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Jan Kratochvíl
中科院分区：
文献类型：
--
作者：
J. Fiala;Jan Kratochvíl
图的L（2，1）-标号是从{0，1，.，t}到它的顶点，使得相邻顶点的标号至少相差2，而距离为2的顶点被赋予不同的标号.我们证明了对allk≥ 3，k-正则图是否允许spank+2的L（2，1）-标号的判定问题是NP-完全的.这回答了R.拉斯卡
AnL(2,1)-labeling of a graph of spantis an assignment of integer labels from {0,1,...,t} to its vertices such that the labels of adjacent vertices differ by at least two, while vertices at distance two are assigned distinct labels.We show that for allk≥ 3, the decision problem whether ak-regular graph admits anL(2,1)-labeling of spank+2 isNP-complete. This answers an open problem of R. Laskar.