Skip to Main content Skip to Navigation

Detection number of bipartite graphs and cubic graphs

Frédéric Havet 1 Nagarajan Paramaguru 2 Rathinaswamy Sampathkumar 3
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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 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.
Document type :
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Frederic Havet <>
Submitted on : Thursday, October 25, 2012 - 5:59:48 PM
Last modification on : Monday, October 12, 2020 - 10:30:20 AM
Long-term archiving on: : Saturday, January 26, 2013 - 2:45:09 AM


Files produced by the author(s)


  • HAL Id : hal-00744365, version 1


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⟩



Record views


Files downloads