Good edge-labelling of graphs.

Julio Araujo 1, 2 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 , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A 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 [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 if a graph G admits a good edge-labelling is NPcomplete, 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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00639005
Contributor : Julio Araujo <>
Submitted on : Monday, November 7, 2011 - 6:51:04 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Document(s) archivé(s) le : Wednesday, February 8, 2012 - 2:36:20 AM

File

goodlab03-with-final-modifs.pd...
Files produced by the author(s)

Identifiers

Collections

Citation

Julio Araujo, Nathann Cohen, Frédéric Giroire, Frédéric Havet. Good edge-labelling of graphs.. Discrete Applied Mathematics, Elsevier, 2012, V Latin American Algorithms, Graphs, and Optimization Symposium -- Gramado, Brazil, 2009, 160 (18), pp.2502-2513. ⟨10.1016/j.dam.2011.07.021⟩. ⟨inria-00639005⟩

Share

Metrics

Record views

332

Files downloads

126