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 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.
Type de document :
Article dans une revue
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>
Liste complète des métadonnées

https://hal.inria.fr/inria-00639005
Contributeur : Julio Araujo <>
Soumis le : lundi 7 novembre 2011 - 18:51:04
Dernière modification le : mercredi 12 décembre 2012 - 11:56:14
Document(s) archivé(s) le : mercredi 8 février 2012 - 02:36:20

Fichier

goodlab03-with-final-modifs.pd...
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.. 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>

Partager

Métriques

Consultations de
la notice

234

Téléchargements du document

88