Skip to Main content Skip to Navigation
Conference papers

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 two distinct vertices u, v, there is at most one (u, v)-path with non-decreasing labels. This notion was introduced in [3] 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: C3-free outerplanar graphs, planar graphs of girth at least 6, subcubic {C3,K2,3}-free graphs.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-00749194
Contributor : Julio Araujo <>
Submitted on : Wednesday, December 12, 2012 - 12:02:44 PM
Last modification on : Monday, October 12, 2020 - 10:30:20 AM
Long-term archiving on: : Wednesday, March 13, 2013 - 2:30:10 AM

File

ext-goodlab.pdf
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. LAGOS'09 - V Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2009, Gramado, Brazil. pp.275-280, ⟨10.1016/j.endm.2009.11.045⟩. ⟨hal-00749194⟩

Share

Metrics

Record views

701

Files downloads

714