## Abstract

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 language | English |
---|---|

Title of host publication | WALCOM |

Subtitle of host publication | Algorithms and Computation - 16th International Conference and Workshops, WALCOM 2022, Proceedings |

Editors | Petra Mutzel, Md. Saidur Rahman, Slamin |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 175-186 |

Number of pages | 12 |

ISBN (Print) | 9783030967307 |

DOIs | |

Publication status | Published - 2022 |

Event | 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 - Jember, Indonesia Duration: 24 Mar 2022 → 26 Mar 2022 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13174 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 16th International Conference and Workshops on Algorithms and Computation, WALCOM 2022 |
---|---|

Country/Territory | Indonesia |

City | Jember |

Period | 24/03/22 → 26/03/22 |

### Bibliographical note

Publisher Copyright:© 2022, Springer Nature Switzerland AG.