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 , 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.
Type de document :
Communication dans un congrès
LAGOS'09 - V Latin-American Algorithms, Graphs and Optimization Symposium, Nov 2009, Gramado, Brazil. Elsevier, Volume 35 (1), pp.275-280, 2009, Eletronic Notes in Discrete Mathematics. <10.1016/j.endm.2009.11.045>
Liste complète des métadonnées


https://hal.inria.fr/hal-00749194
Contributeur : Julio Araujo <>
Soumis le : mercredi 12 décembre 2012 - 12:02:44
Dernière modification le : jeudi 9 juillet 2015 - 14:43:00
Document(s) archivé(s) le : mercredi 13 mars 2013 - 02:30:10

Fichier

ext-goodlab.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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. Elsevier, Volume 35 (1), pp.275-280, 2009, Eletronic Notes in Discrete Mathematics. <10.1016/j.endm.2009.11.045>. <hal-00749194>

Partager

Métriques

Consultations de
la notice

327

Téléchargements du document

114