Detection number of bipartite graphs and cubic graphs

For a connected graph G of order |V(G)| ≥ 3 and a k-labelling c : E(G) → {1,2, . . . ,k} of the edges of G, the code of a vertex v of G is the ordered k-tuple (ℓ1, ℓ2, . . . , ℓk), where ℓi is the number of edges incident with v that are labelled i. The k-labelling c is detectable if every two adjacent vertices of G have distinct codes. The minimum positive integer k for which G has a detectable k-labelling is the detection number of G. In this paper, we show that it is NP-complete to decide if the detection number of a cubic graph is 2. We also show that the detection number of every bipartite graph of minimum degree at least 3 is at most 2. Finally, we give some sufficient condition for a cubic graph to have detection number 3.; 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.