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

Description

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.

Abstract

International audience

Additional details