Characterizing identifying codes from the spectrum of a graph or digraph

Abstract

A (1, ≤ ℓ)-identifying code in digraph D is a dominating subset C of vertices of D, such that all distinct subsets of vertices of D with cardinality at most ℓ have distinct closed in-neighborhoods within C. As far as we know, it is the very first time that the spectral graph theory has been applied to the identifying codes. We give a new method to obtain an upper bound on ℓ for digraphs. The results obtained here can also be applied to graphs.

This research is supported by the Catalan Research Council under project 2014SGR1147. The second and third authors have also received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.