Good edge-labelling of graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Good edge-labelling of graphs

Résumé

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.
Fichier principal
Vignette du fichier
RR-6934.pdf (372.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00383343 , version 1 (12-05-2009)
inria-00383343 , version 2 (14-05-2009)
inria-00383343 , version 3 (14-05-2009)
inria-00383343 , version 4 (15-05-2009)

Identifiants

  • HAL Id : inria-00383343 , version 2

Citer

Julio Araújo, Nathann Cohen, Frédéric Giroire, Frédéric Havet. Good edge-labelling of graphs. [Research Report] RR-6934, 2009, pp.16. ⟨inria-00383343v2⟩
251 Consultations
762 Téléchargements

Partager

Gmail Facebook X LinkedIn More