Idioma:

On the Minimum Size of an Identifying Code Over All Orientations of a Graph

Cohen, Nathann ; Havet, Frédéric

The Electronic journal of combinatorics, 2018-03, Vol.25 (1) [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
On the Minimum Size of an Identifying Code Over All Orientations of a Graph
Autor: Cohen, Nathann ; Havet, Frédéric
Assuntos: Computer Science ; Discrete Mathematics
É parte de: The Electronic journal of combinatorics, 2018-03, Vol.25 (1)
Descrição: 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$.
Editor: Open Journal Systems
Idioma: Inglês

Links

Voltar para lista de resultados