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

Gaétan Berthe, Barnaby Martin*, Daniël Paulusma, Siani Smith

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

1 Citation (Scopus)


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)-Edge-Labelling was only partially classified in the literature. We complete this study for all p, q≥ 0 by showing that whenever (p, q) ≠ (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.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings
EditorsPetra Mutzel, Md. Saidur Rahman, Slamin
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages12
ISBN (Print)9783030967307
Publication statusPublished - 2022
Event16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 - Jember, Indonesia
Duration: 24 Mar 202226 Mar 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13174 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022

Bibliographical note

Publisher Copyright:
© 2022, Springer Nature Switzerland AG.


Dive into the research topics of 'The Complexity of L(p, q)-Edge-Labelling'. Together they form a unique fingerprint.

Cite this