QA228 : R-identifying codes and their density in some special graphs
Thesis > Central Library of Shahrood University > Mathematical Sciences > MSc > 2014
Authors:
Abstarct: Consider a connected undirected graph G = (V, E), a subset of vertices C ⊆ V ,and
an integer r ≥ 1; for any vertex v ∈ V ,let Br(v) denote the ball of radius r
centered at v, i.e., the set of all vertices within distance r from v. If for all vertices
v ∈ V (respectively, v ∈ V \C), the sets Br(v) ∩ C are all nonempty and different,
then we call C an r-identifying code (respectively, an r-locating-dominating code).
We study the smallest cardinalities or densities of these codes in this dissertation.
In the first chapter of this dissertation, we state required definitions and theorems
of graph theory. In Chapter 2, we describe some properties of translations in
Z2, properties which will be necessary to our study of periodic codes in the four
grids including square lattice, triangular lattice, king lattice and hexagonal grid
for small r. In Chapter 3, We prove here that for all r > 1, D(Gk, r) = 4 1 r. In
Chapter 4, we determine the exact value of the smallest possible density of an
r-identifying code and r-locating-dominating code in the finite and infinite chains
and finite cycles , for all r ≥ 1.
Keywords:
#Identifyig code #Locating Dominatin code #Graph Link
Keeping place: Central Library of Shahrood University
Visitor:
Keeping place: Central Library of Shahrood University
Visitor: