Good edge-labelling of graphs

AbstractA 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 by Bermond et al. (2009) [2] 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 whether a graph G admits a good edge-labelling is NP-complete, even if G is bipartite. Finally, we give large classes of graphs admitting a good edge-labelling: C3-free outerplanar graphs, planar graphs of girth at least 6, {C3,K2,3}-free subcubic graphs and {C3,K2,3}-free ABC-graphs