Good edge-labelling of graphs

Julio Araújo 1 Nathann Cohen 1 Frédéric Giroire 1 Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A {\em good edge-labelling} of a graph $G$ is a labelling of its edges such that, for any ordered pair of vertices $(x,y)$, there do not exist two paths from $x$ to $y$ with increasing labels. This notion was introduced in~\cite{BCP} to solve wavelength assignment problems for specific categories of graphs. In this paper, we aim at characterizing the class of graphs that admit a good edge-labelling. First, we exhibit infinite families of graphs for which no such edge-labelling can be found. We then show that deciding if a graph admits a good edge-labelling is NP-complete. Finally, we give large classes of graphs admitting a good edge-labelling: forests, $C_3$-free outerplanar graphs, planar graphs of girth at least 6, subcubic $\{C_3,K_{2,3}\}$-free graphs.
Type de document :
Rapport
[Research Report] RR-6934, INRIA. 2009, pp.16
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00383343
Contributeur : Nathann Cohen <>
Soumis le : vendredi 15 mai 2009 - 19:08:26
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : samedi 26 novembre 2016 - 09:20:45

Fichier

RR-6934.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00383343, version 4

Citation

Julio Araújo, Nathann Cohen, Frédéric Giroire, Frédéric Havet. Good edge-labelling of graphs. [Research Report] RR-6934, INRIA. 2009, pp.16. 〈inria-00383343v4〉

Partager

Métriques

Consultations de la notice

447

Téléchargements de fichiers

138