28585 articles – 22073 Notices  [english version]

inria-00383343, version 4

## Good edge-labelling of graphs

Julio Araújo () 1, Nathann Cohen () 1, Frédéric Giroire () 1, Frédéric Havet () 1

N° RR-6934 (2009)

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.

• 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
• INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271

• inria-00383343, version 4
• oai:hal.inria.fr:inria-00383343
• Contributeur :
• Soumis le : Vendredi 15 Mai 2009, 19:08:26
• Dernière modification le : Vendredi 15 Mai 2009, 20:22:35