Improved Upper Bounds for Identifying Codes in n-dimensional q-ary Cubes

Autor: B. N. Waphare, N. V. Shinde
Rok vydání: 2020
Předmět:
Zdroj: International Journal of Applied and Computational Mathematics. 6
ISSN: 2199-5796
2349-5103
DOI: 10.1007/s40819-020-0795-8
Popis: For a simple, undirected graph G with vertex set V, a subset D of V is called as an identifying code in G if the sets $$N[u]\bigcap D$$ are nonempty and distinct for all u in G, where N[u] is a set of its neighbors along with itself. In this paper, we construct identifying codes in an n-dimensional cube $$Z_{q_1}\square Z_{q_2}\square \dots \square Z_{q_n} $$, where $$Z_{q_i}(1\le i\le n)$$ is the ring of integers modulo $$q_i$$. The minimum number of vertices in an identifying code in $$Z_{q_1}\square Z_{q_2}\square \dots \square Z_{q_n}$$ is denoted by $$M_{(q_1,q_2,\ldots ,q_n)}^n$$ and that in $${Z_q}^n$$ is denoted by $$M_q^n$$. We improve upper bounds on $$M_q^n$$ by constructing identifying codes in $${Z_q}^n$$. Also, we find the exact value of $$M_{(q_1,q_2,q_3)}^3$$ for even integers $$q_1,q_2,q_3>4$$ and an upper bound on $$M_{(q_1,q_2,\ldots ,q_n)}^n$$ for even integers $$q_i>4, 1\le i\le n$$. In addition, we give few sufficient conditions on a subset of the vertex set of a graph G to be an identifying code in G.
Databáze: OpenAIRE
Externí odkaz: