Skip to Main content Skip to Navigation
New interface
Journal articles

On the minimum size of an identifying code over all orientations of a graph

Nathann Cohen 1 Frédéric Havet 2 
1 GALaC - LRI - Graphes, Algorithmes et Combinatoire (LRI)
LRI - Laboratoire de Recherche en Informatique
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : If G be a graph or a digraph, let id(G) be the minimum size of an identifying code of G if one exists, and id(G) = +∞ otherwise. For a graph G, let idor(G) be the minimum of id(D) overall orientations D of G. We give some lower and upper bounds on idor(G). In particular, we show that idor(G) <= 3/2 id(G) for every graph G. We also show that computing idor(G) is NP-hard, while deciding whether idor(G) <= |V (G)| − k is polynomial-time solvable for every fixed integer k.
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Friday, April 13, 2018 - 7:17:12 AM
Last modification on : Tuesday, October 25, 2022 - 4:18:30 PM


Files produced by the author(s)


  • HAL Id : hal-01765643, version 1


Nathann Cohen, Frédéric Havet. On the minimum size of an identifying code over all orientations of a graph. The Electronic Journal of Combinatorics, 2018, 25 (1), pp.#P1.49. ⟨hal-01765643⟩



Record views


Files downloads