If $G$ be a graph or a digraph, let $\mathrm{id}(G)$ be the minimum size of an identifying code of $G$ if one exists, and $\mathrm{id}(G)=+\infty$ otherwise. For a graph $G$, let $\mathrm{idor}(G)$ be the minimum of $\mathrm{id}(D)$ overall orientations $D$ of $G$. We give some lower and upper bounds on $\mathrm{idor}(G)$. In particular, we show that $\mathrm{idor}(G)\leqslant \frac{3}{2} \mathrm{id}(G)$ for every graph $G$. We also show that computing $\mathrm{idor}(G)$ is NP-hard, while deciding whether $\mathrm{idor}(G)\leqslant |V(G)|-k$ is polynomial-time solvable for every fixed integer $k$.
@article{10_37236_7117,
author = {Nathann Cohen and Fr\'ed\'eric Havet},
title = {On the minimum size of an identifying code over all orientations of a graph},
journal = {The electronic journal of combinatorics},
year = {2018},
volume = {25},
number = {1},
doi = {10.37236/7117},
zbl = {1392.05105},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7117/}
}
TY - JOUR
AU - Nathann Cohen
AU - Frédéric Havet
TI - On the minimum size of an identifying code over all orientations of a graph
JO - The electronic journal of combinatorics
PY - 2018
VL - 25
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7117/
DO - 10.37236/7117
ID - 10_37236_7117
ER -
%0 Journal Article
%A Nathann Cohen
%A Frédéric Havet
%T On the minimum size of an identifying code over all orientations of a graph
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7117/
%R 10.37236/7117
%F 10_37236_7117
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, Tome 25 (2018) no. 1. doi: 10.37236/7117
