Detection number of bipartite graphs and cubic graphs
Frederic Havet, Nagarajan Paramaguru, Rathinasamy Sampathkumar
Abstract
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
det(G) 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.
Full Text: PDF PostScript