Detection number of bipartite graphs and cubic graphs

Résumé : Pour un graphe connexe G d'ordre |V(G)| ≥ 3 et un étiquetage c : E(G) → {1,2, . . . ,k} des arêtes de G, le code d'un sommet v de G est le k-uplet (ℓ1, ℓ2, . . . , ℓk), où ℓi est le nombre d'arêtes incidentes à v qui sont étiquetées i. Le k-étiquetage c est détectable si, quels que soient deux sommets adjacents de G, leurs codes sont distincts. Le plus petit entier strictement positif k pour lequel G a un k-étiquetage détectable est l'indice de détection det(G) de G. Dans ce rapport, nous montrons qu'il est NP-complet de décider si l'indice de détection d'une graphe cubique vaut 2. Nous montrons également que l'indice de détection de tout graphe biparti de degré minimum au moins 3 est au plus 2. Enfin, nous donnons des conditions suffisantes pour qu'un graphe cubique soit d'indice de détection 3.
Type de document :
Rapport
[Research Report] RR-8115, INRIA. 2012, pp.17
Liste complète des métadonnées

https://hal.inria.fr/hal-00744365
Contributeur : Frederic Havet <>
Soumis le : jeudi 25 octobre 2012 - 17:59:48
Dernière modification le : samedi 17 septembre 2016 - 01:35:28
Document(s) archivé(s) le : samedi 26 janvier 2013 - 02:45:09

Fichier

RR-8115.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00744365, version 1

Collections

Citation

Frédéric Havet, Nagarajan Paramaguru, Rathinaswamy Sampathkumar. Detection number of bipartite graphs and cubic graphs. [Research Report] RR-8115, INRIA. 2012, pp.17. <hal-00744365>

Partager

Métriques

Consultations de
la notice

231

Téléchargements du document

170