Characterizing identifying codes from the spectrum of a graph or digraph

Balbuena, C.; Dalfó, Cristina; Martínez Barona, B.

doi:https://doi.org/10.1016/j.laa.2019.02.010

View/Open

Postprint (374.1Kb)
Sol·licita una còpia

Issue date

2019

Author

Balbuena, C.

Dalfó, Cristina

Martínez Barona, B.

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.