QA576 : On the number and minimum size of identifying codes over graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2020
Authors:
Atefeh Moussavi [Author], Meysam Alishahi[Supervisor], Abdollah Alhevaz[Supervisor], Ebrahim Hashemi[Advisor]
Abstarct: Let G be a simple graph with vertex set v∈V and r≥1, we denote by B_(G,r) (v) the ball of radius r and center v. A set C⊆V is said to be an r-identifying code in G if the sets B_(G,r) (v)∩C, for v∈V are all nonempty and distinict. A graph G which admits an r-identifying code is called r-identifiable, and in this case the smallest size of an r-identifying code in G is dented by γ_r^ID (G). We study the number of different optimal r-identifying codes C, i.e., such that |C|=γ_r^ID (G), that a graph G can admit, and try to construct graphs having many such codes. For a graph G, let idor(G) be the minimum of id(D) over all orientations D of G. We give some lower and upper bounds on idor(G). In particular, we show that idor(G)≤3/2 id(G) for every graph G. We also show that computing idor(G) is NP-hard, while deciding whether idor(G)≤|V(G)|-k is polynomial-time solvable for every fixed integer k.
Keywords:
#Identifying code #Identifiable graphs #orientation #Twin-free graphs #NP-complete Keeping place: Central Library of Shahrood University
Visitor: