We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The Complexity of L(p,q)-Edge-Labelling

Berthe, G. and Martin, B. and Paulusma, D. and Smith, S. (2022) 'The Complexity of L(p,q)-Edge-Labelling.', The 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021) University of Jember, East Java, 24-26 Mar 2022.


The L(p, q)-Edge-Labelling problem is the edge variant of the well-known L(p, q)-Labelling problem. It is equivalent to the L(p, q)-Labelling problem itself if we restrict the input of the latter problem to line graphs. So far, the complexity of L(p, q)-EdgeLabelling was only partially classified in the literature. We complete this study for all p, q ≥ 0 by showing that whenever (p, q) 6= (0, 0), the L(p, q)-Edge-Labelling problem is NP-complete. We do this by proving that for all p, q ≥ 0 except p = q = 0, there is an integer k so that L(p, q)-Edge-k-Labelling is NP-complete.

Item Type:Conference item (Paper)
Full text:Publisher-imposed embargo
(AM) Accepted Manuscript
File format - PDF
Publisher Web site:
Date accepted:20 November 2021
Date deposited:20 December 2021
Date of first online publication:2022
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar