QA598 : Applying graph spectra to characterizing the identifying codes
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2021
Authors:
Hila Aghania [Author], Abdollah Alhevaz[Supervisor]
Abstarct: A (1.≤ l)-identifying code in a digraph D is a subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In this thesis, we give some sufficient conditions for a digraph of minimum in-degree δ - ≥ 1 to admit a (1.≤ l)- identifying code for l ∈ {〖δ 〗^-.〖δ 〗^-+ 1}. As a corollary, we obtain the result by Laihonen that states that a graph of minimum degree δ ≥ 2 and girth at least 7 admits a (1.≤ δ)-identifying code. Moreover, we prove that every 1-in-regular digraph has a (1.≤ 2)-identifying code if and only if the girth of the digraph is at least 5. We also characterize all the 2-in-regular digraphs admitting a (1.≤ l)-identifying code for l ∈ {2.3}, and give a new characterization of identifying codes using the spectral properties of digraphs. Moreover, we give a new method to obtain an upper bound on l for digraphs. All the results of this thesis can also be applied to graphs.
Keywords:
#Graph #Digraph #Identifying code #Adjacency matrix #Spectrum #Eigenvectors. Keeping place: Central Library of Shahrood University
Visitor: