论文标题
L（P，Q） - 边缘标签的复杂性
The complexity of L(p,q)-Edge-Labelling
论文作者
论文摘要
我们考虑L（p，q） - 边缘标记问题，这是众所周知的L（P，Q） - 标志性问题的边缘变体。到目前为止，此问题的复杂性仅部分分类。我们通过证明（p，q）不是（0,0），l（p，q） - edge-egger-labeling问题是NP完整的，我们可以完成所有非负P和Q的研究。我们通过证明所有非负P和Q的证明，除了p = q = 0，存在一个整数k，以便l（p，q） - edge-k-labering是np complete。
We consider the L(p,q)-Edge-Labelling problem, which is the edge variant of the well-known L(p,q)-Labelling problem. So far, the complexity of this problem was only partially classified. We complete this study for all nonnegative p and q, by showing that, whenever (p,q) is not (0,0), L(p,q)-Edge-Labelling problem is NP-complete. We do this by proving that for all nonnegative p and q, except p=q=0, there exists an integer k so that L(p,q)-Edge-k-Labelling is NP-complete.
