Covering codes of a graph associated to a finite vector space
UDC 512.5 In this paper, we investigate the problem of covering the vertices of a graph associated to a finite vector space as introduced by Das [Commun. Algebra, 44, 3918 – 3926 (2016)], such that we can uniquely identify any vertex by examining the vertices that cover it. We use locating-dominatin...
Gespeichert in:
| Datum: | 2020 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2020
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/652 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860507077068193792 |
|---|---|
| author | Murtaza, M. Javaid, I. Fazil , M. Murtaza, M. Javaid, I. Fazil , M. |
| author_facet | Murtaza, M. Javaid, I. Fazil , M. Murtaza, M. Javaid, I. Fazil , M. |
| author_sort | Murtaza, M. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2022-03-26T11:01:53Z |
| description | UDC 512.5
In this paper, we investigate the problem of covering the vertices of a graph associated to a finite vector space as introduced by Das [Commun. Algebra, 44, 3918 – 3926 (2016)], such that we can uniquely identify any vertex by examining the vertices that cover it. We use locating-dominating sets and identifying codes, which are closely related concepts for this purpose. We find the location-domination number and the identifying number of the graph and study the exchange property for locating-dominating sets and identifying codes. |
| doi_str_mv | 10.37863/umzh.v72i7.652 |
| first_indexed | 2026-03-24T02:03:34Z |
| format | Article |
| fulltext |
DOI: 10.37863/umzh.v72i7.652
UDC 512.5
M. Murtaza, I. Javaid, M. Fazil (Centre Adv. Stud. Pure and Appl. Math.,
Bahauddin Zakariya Univ., Multan, Pakistan)
COVERING CODES OF A GRAPH ASSOCIATED TO A FINITE VECTOR SPACE
КОДИ ПОКРИТТЯ ГРАФА, ЩО ПОВ’ЯЗАНИЙ ЗI СКIНЧЕННИМ
ВЕКТОРНИМ ПРОСТОРОМ
In this paper, we investigate the problem of covering the vertices of a graph associated to a finite vector space as introduced
by Das [Commun. Algebra, 44, 3918 – 3926 (2016)], such that we can uniquely identify any vertex by examining the
vertices that cover it. We use locating-dominating sets and identifying codes, which are closely related concepts for this
purpose. We find the location-domination number and the identifying number of the graph and study the exchange property
for locating-dominating sets and identifying codes.
Дослiджується задача покриття вершин графа, що пов’язаний iз скiнченним векторним простором, як це визна-
чено у A. Das [Commun. Algebra, 44, 3918 – 3926 (2016)], так що ми можемо однозначно iдентифiкувати будь-яку
вершину за вершинами, що її накривають. У цiй роботi використовуються розмiщенi домiнуючi множини, а також
iдентифiкацiйнi коди, якi у даному випадку є дуже близькими поняттями. Знайдено число розмiщеного домiну-
вання й iдентифiкацiйне число для графа, а також вивчено властивiсть обмiну для розмiщених домiнуючих та
iдентифiкацiйних кодiв.
1. Preliminaries. The association of graphs to algebraic structures has become an interesting
research topic for the past few decades. See for instance: commuting graphs for groups [2, 6, 21],
power graphs for groups and semigroups [8, 10, 26], zero divisor graph associated to a commutative
ring [1, 3]. The association of a graph and vector space has history back in 1958 by Gould [18].
Later, Chen [13] investigated on vector spaces associated with a graph. Carvalho [9] studied vector
space and the Petersen graph. In the recent past, Manjula [25] used vector spaces and made it possible
to use techniques of linear algebra in studying the graph. Intersection graphs assigned to vector space
were studied [22, 32]. Das [15] introduced a new graph structure, called non-zero component graph
on finite dimensional vector spaces. He showed that the graph is connected and found its domination
number and independence number [16]. He characterized the maximal cliques in the graph and
found the exact clique number, for some particular cases [16]. Das has also given some results on
size, edge-connectivity and the chromatic number of the graph [16]. For more work on the non-zero
component graph, see [27, 33].
The covering code problem for a given graph involves finding a set of vertices with the minimum
cardinality whose neighborhoods uniquely overlap at any given graph vertex. The problem has
demonstrated its fundamental nature through a wide variety of applications. Locating-dominating
sets were introduced by Slater [29, 31] and identifying codes by Karpovsky et al. [23]. Locating-
dominating sets are very similar to identifying codes with the subtle difference that only the vertices
not in the locating-dominating set are required to have unique identifying sets. The decision problem
for locating-dominating sets for directed graphs has been shown to be an NP-complete problem [11].
A considerable literature has been developed in this field (see [5, 12, 14, 17, 20, 28 – 30, 34]). In [7],
it was pointed out that each locating-dominating set is both locating and dominating set. However, a
set that is both locating and dominating is not necessarily a locating-dominating set.
c\bigcirc M. MURTAZA, I. JAVAID, M. FAZIL, 2020
952 ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
COVERING CODES OF A GRAPH ASSOCIATED TO A FINITE VECTOR SPACE 953
The initial application of locating-dominating sets and identifying codes was fault-diagnosis in
the maintenance of multiprocessor systems [23]. More recently, identifying codes and locating-
dominating sets were extended to applications for joint monitoring and routing in wireless sensor
networks [24] and environmental monitoring [4].
A natural question arises in reader’s mind that how can we distinguish the need of identifying
codes or locating-dominating sets for a system? A system, in which processors or sensors are able
to send the information about themselves and their neighbors, an identifying code is necessary.
However, the systems where the sensors work without failure or if their only task is to test their
neighborhoods (not themselves) then we shall search for locating-dominating sets. Moreover, the
existence of identifying codes is not always guaranteed in a graph (as we shall see in our later
discussion) and then a locating-dominating set is the next best alternative.
In this paper, we study the locating-dominating sets and identifying codes for the graph associated
to finite vector space as defined in [15]. Also, we find location-domination number and identifying
number of the graph and study the exchange property of the graph for these graph invariants.
Now, we recall some definitions of graph theory which are necessary for this article. We use
\Gamma to denote a connected graph with vertex set V (\Gamma ) and edge set E(\Gamma ). The degree of the vertex
v in \Gamma , denoted by deg(v), is the number of edges to which v belongs. The open neighborhood
of the vertex u of \Gamma is N(u) = \{ v \in V (\Gamma ) : uv \in E(\Gamma )\} and the closed neighborhood of u is
N [u] = N(u) \cup \{ u\} .
Formally, we define a locating-dominating set as: A set LD of vertices of \Gamma is called a locating-
dominating set for \Gamma if for every two distinct vertices u, v \in V (\Gamma )\setminus LD, we have \varnothing \not = N(u)\cap LD \not =
\not = N(v) \cap LD \not = \varnothing . The location-domination number, denoted by \lambda (\Gamma ), is the minimum cardinality
of a locating-dominating set of \Gamma .
An identifying code is a subset of vertices in a graph with the property that the neighborhood of
every vertex has a unique intersection with the code. Formally it is defined as: A set ID is called
an identifying code for the graph \Gamma if N [u] \cap ID \not = N [v] \cap ID for all u, v \in V (\Gamma ). The minimum
cardinality of an identifying code is called the identifying number of \Gamma and we denote it by I(\Gamma ).
Unlike identifying codes, every graph has a trivial locating-dominating set, the entire set of
vertices. On the other hand, a graph may not have an identifying code, because if N [u] = N [v] for
some u, v \in V (\Gamma ), then clearly V (\Gamma ) is not an identifying code. Since an identifying code is also a
locating-dominating set, therefore
\lambda (\Gamma (\BbbV )) \leq I(\Gamma (\BbbV )). (1)
Two vertices u, v are adjacent twins if N [u] = N [v] and non-adjacent twins if N(u) = N(v). If
u, v are adjacent or non-adjacent twins, then u, v are twins. A set of vertices T is called a twin-set
if any two of its vertices are twins [19]. By definition of twin vertices and twin-set, we have the
following straightforward results.
Proposition 1.1. Suppose that u, v are twins in a connected graph \Gamma and LD is a locating-
dominating set of \Gamma , then either u or v is in LD. Moreover, if u \in LD and v \not \in LD, then
(LD \setminus \{ u\} ) \cup \{ v\} is a locating-dominating set of \Gamma .
Proposition 1.2. Let T be a twin-set of order m \geq 2 in a connected graph \Gamma . Then every
locating-dominating set LD of \Gamma contains at least m - 1 vertices of T.
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
954 M. MURTAZA, I. JAVAID, M. FAZIL
1.1. Non-zero component graph. Let \BbbV be a vector space over a field \BbbF with a basis
\{ b1, b2, . . . , bn\} . A vector v \in \BbbV can be expressed uniquely as a linear combination of the form
v = c1b1+c2b2+ . . .+cnbn. A non-zero component graph, denoted by \Gamma (\BbbV ), can be associated with
a finite dimensional vector space in the following way: the vertex set of the graph \Gamma (\BbbV ) consists
of the non-zero vectors and two vertices are joined by an edge if they share at least one bi with
non-zero coefficient in their unique linear combination with respect to \{ b1, b2, . . . , bn\} [15]. It is
proved in [15] that \Gamma (\BbbV ) is independent of the choice of basis, i.e., isomorphic non-zero component
graphs are obtained with two different bases.
b
1
b
3
b
2
b
1 + b
2
b
1 + b
3
b
2 + b
3
b
1 +b
2+b
3
Fig. 1. \mathrm{d}\mathrm{i}\mathrm{m}(\BbbV ) = 3, \BbbF = Z2 = \{ 0, 1\} .
Theorem 1.1 [16]. If \BbbV be an n-dimensional vector space over a finite field \BbbF with q elements,
then the order of \Gamma (\BbbV ) is qn - 1 and the size of \Gamma (\BbbV ) is
q2n - qn + 1 - (2q - 1)n
2
.
Theorem 1.2 [15]. Let \BbbV be an n-dimensional vector space over a finite field \BbbF with q elements
and \Gamma (\BbbV ) be its associated graph with respect to a basis \{ b1, b2, ..., bn\} , then a vertex having s non-
zero coefficients in its unique linear combination of basis vector has degree (qs - 1)qn - s - 1.
2. Locating-dominating sets and identifying codes of non-zero component graph. In this
section, we study the location-domination number of non-zero component graph \Gamma (\BbbV ).
We partition the vertex set of \Gamma (\BbbV ) into n classes Ti, where Ti = \{ v \in \BbbV : v is a linear
combination of basis vectors with i non-zero coefficients\} . For example, if n = 3 and q = 2, then
T2 = \{ b1 + b2, b2 + b3, b1 + b3\} (see Fig. 1).
Lemma 2.1. Let \BbbV be a vector space of dimension n over a field \BbbF of 2 elements. If v \in Ts
for s, 1 \leq s \leq n, then, for an r, 1 \leq r \leq n,
| N(v) \cap Tr| =
\left\{
\biggl(
n
r
\biggr)
-
\biggl(
n - s
r
\biggr)
- 1 if r \leq n - s and r = s,\biggl(
n
r
\biggr)
-
\biggl(
n - s
r
\biggr)
if r \leq n - s and r \not = s,\biggl(
n
r
\biggr)
- 1 if n - s < r \leq n and r = s,\biggl(
n
r
\biggr)
if n - s < r \leq n and r \not = s.
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
COVERING CODES OF A GRAPH ASSOCIATED TO A FINITE VECTOR SPACE 955
Proof. We consider the following cases for r:
1. If r \leq n - s, then
\biggl(
n - s
r
\biggr)
elements of Tr have s zero coefficients in their unique linear
combination of basis vectors for those s basis vectors which have the non-zero coefficients in the
unique linear combination of v, and hence these elements of Tr are not adjacent to v. Thus, | N(v)\cap
\cap Tr| =
\biggl(
n
r
\biggr)
-
\biggl(
n - s
r
\biggr)
or
\biggl(
n
r
\biggr)
-
\biggl(
n - s
r
\biggr)
- 1 according as r \not = s or r = s, respectively.
2. If r > n - s, then each element of Tr will have at least one non-zero coefficient in its unique
linear combination of basis vectors for those s basis vectors which have the non-zero coefficients in
the unique linear combination of v, and hence v is adjacent to all elements of Tr. Thus, | N(v)\cap Tr| =
=
\biggl(
n
r
\biggr)
or
\biggl(
n
r
\biggr)
- 1 according as r \not = s or r = s, respectively.
Lemma 2.1 is proved.
Let v \in Ts, then it can be seen from Lemma 2.1 that
\mathrm{d}\mathrm{e}\mathrm{g}(v) =
\Biggl[
n\sum
r=1
| N(v) \cap Tr|
\Biggr]
- 1 =
=
n - s\sum
r=1
\biggl[ \biggl(
n
r
\biggr)
-
\biggl(
n - s
r
\biggr) \biggr]
+
n\sum
r=n - s+1
\biggl(
n
r
\biggr)
- 1 = (2s - 1)2n - s - 1
which is consistent with Theorem 1.2 for q = 2.
Remark 2.1. Let \BbbV be a vector space of dimension n over a field \BbbF of 2 elements. If v \in Ts
for s, 1 \leq s \leq n, then \mathrm{d}\mathrm{e}\mathrm{g}(v) = (2s - 1)2n - s - 1.
Lemma 2.2. Let \BbbV be a vector space of dimension n \geq 4 over a field \BbbF of 2 elements. If
u, v \in V (\Gamma (\BbbV )) \setminus Tn - 1, then N(u) \cap T2 \not = N(v) \cap T2.
Proof. Since u \in Tr and v \in Ts for some 1 \leq r, s \leq n, r, s \not = n - 1, therefore u has r non-
zero coefficients in its unique linear combination of basis vectors B = \{ b1, b2, . . . , bn\} . Let Bu \subseteq B
and Bv \subseteq B be the sets of those basis vectors which have non-zero coefficients in the unique linear
combination of basis vectors for u and v, respectively. Then u is not adjacent to
\biggl(
n - r
2
\biggr)
elements
of T2 which have exactly two non-zero coefficients of basis vectors in Bu and zero coefficients of
basis vectors in B \setminus Bu. Since u \not \in Tn - 1, therefore such elements exist in T2 which have exactly
two non-zero coefficients of basis vectors of Bu. Thus, N(u)\cap T2 = T2 \setminus \{ two element sum of basis
vectors in B \setminus Br\} . Since u \not = v, therefore Bu \not = Bv and, hence, N(u) \cap T2 \not = N(v) \cap T2.
Lemma 2.2 is proved.
An immediate consequence of Lemma 2.2 is that the set T2 \cup Tn - 1 forms a locating-dominating
set for \Gamma (\BbbV ) for a vector space \BbbV of dimension n \geq 4 over a field of 2 elements.
Since the elements of Tn - 1 have non-zero coefficients for n - 1 basis vectors, therefore we
use the notation uj =
\sum n
i=1
bi - bj in the proof of Lemma 2.3 for the elements of Tn - 1 which
have zero coefficient for the basis vector bj . Also, N [uj ] = V (\Gamma (\BbbV )) \setminus \{ bj\} , therefore two elements
ui, uj \in Tn - 1 have same neighbors in \Gamma (\BbbV ) except the elements bi and bj of T1.
Lemma 2.3. Let \BbbV be a vector space of dimension n \geq 3 over a field \BbbF of 2 elements. Let LD
be a locating-dominating set for \Gamma (\BbbV ) and | LD \cap T1| = s.
(a) If 0 \leq s \leq n - 2, then | LD \cap Tn - 1| \geq n - s.
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
956 M. MURTAZA, I. JAVAID, M. FAZIL
(b) If s = n - 1, then | LD \cap \{ Tn \cup Tn - 1\} | \geq 1.
Proof. Without loss of generality assume that LD \cap T1 = \{ b1, b2, . . . , bs\} .
(a) Let ui, uj \in Tn - 1 for s + 1 \leq i \not = j \leq n be two distinct elements of Tn - 1, then
N(ui) \cap \{ LD \cap T1\} = N(uj) \cap \{ LD \cap T1\} = \varnothing . Since ui and uj have different neighbors only in
\{ bs+1, bs+2, . . . , bn\} \subseteq T1 which is not subset of LD, therefore these n - s elements of Tn - 1 must
belong to LD. Hence, | LD \cap Tn - 1| \geq n - s.
(b) Let un \in Tn - 1 and v \in Tn, then N(un) \cap \{ LD \cap T1\} = N(v) \cap \{ LD \cap T1\} = \varnothing . Since un
and v have only one different neighbor bn \in T1 which is not in LD, therefore either un or v must
belong to LD.
Lemma 2.3 is proved.
Corollary 2.1. Let \BbbV be a vector space of dimension n \geq 3 over a field \BbbF of 2 elements. Let
LD be a locating-dominating set for \Gamma (\BbbV ), then | LD| \geq n.
Proof. If 0 \leq s \leq n - 2, then | LD \cap \{ T1 \cup Tn - 1\} | \geq s + n - s = n by Lemma 2.3(a). If
s = n - 1, then | LD \cap \{ T1 \cup Tn - 1 \cup Tn\} | \geq n - 1+ 1 = n by Lemma 2.3(b). If s = n, then clearly
| LD \cap T1| = n.
Since \lambda (P3) = 2, where P3 is the path graph of order 3, therefore we have the following
proposition.
Proposition 2.1. Let \BbbV be a vector space of dimension 2 over a field \BbbF of 2 elements, then
\lambda (\Gamma (\BbbV )) = 2.
Let \BbbV be a vector space of dimension n and q \geq 3. Then class Ti for each i, 1 \leq i \leq n, has\biggl(
n
i
\biggr)
twin subsets of vertices of \Gamma (\BbbV ) and each of these twin subsets has the cardinality (q - 1)i.
We use the notation Tik where 1 \leq k \leq
\biggl(
n
i
\biggr)
to denote the kth twin set in the class Ti.
Theorem 2.1. Let \BbbV be a vector space over a field \BbbF of q elements with \{ b1, b2, . . . , bn\} as
basis:
(a) If q = 2 and n \geq 3, then \lambda (\Gamma (\BbbV )) = n.
(b) If q \geq 3, then \lambda (\Gamma (\BbbV )) =
\sum n
i=1
\biggl(
n
i
\biggr)
((q - 1)i - 1).
Proof. (a) For q = 2 and n \geq 3, we first prove that T1 is a locating-dominating set for \Gamma (\BbbV ).
Let u, v \in V (\Gamma (\BbbV )) \setminus T1. If u, v \in Ts for some s when 2 \leq s \leq n - 1, then both u and v have s
non-zero coefficients in their linear combinations of basis vectors. Since u \not = v and s < n, therefore
\varnothing \not = N(u) \cap T1 \not = N(v) \cap T1 \not = \varnothing . If u \in Tr and v \in Ts for some r, s 2 \leq r \not = s \leq n, then
| N(u)\cap T1| \not = | N(v)\cap T1| by Lemma 2.1, and, hence, \varnothing \not = N(u)\cap T1 \not = N(v)\cap T1 \not = \varnothing . Thus, T1
is a locating dominating set for \Gamma (\BbbV ). Hence, \lambda (\Gamma (\BbbV )) \leq n. Also, \lambda (\Gamma (\BbbV )) \geq n by Corollary 2.1.
(b) If q \geq 3, then from Proposition 1.2, a minimal locating-dominating set of \Gamma (\BbbV ) contains
at least (q - 1)i - 1 vertices from Tik for each i, 1 \leq i \leq n and each k, 1 \leq k \leq
\biggl(
n
i
\biggr)
, and
hence \lambda (\Gamma (\BbbV )) \geq
\sum n
i=1
\biggl(
n
i
\biggr)
((q - 1)i - 1). Moreover, a subset of \Gamma (\BbbV ) of cardinality greater than\sum n
i=1
\biggl(
n
i
\biggr)
((q - 1)i - 1) has all the vertices of at least one twin subset Tik . Thus, from Proposition
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
COVERING CODES OF A GRAPH ASSOCIATED TO A FINITE VECTOR SPACE 957
1.1, a locating-dominating set of cardinality greater than
\sum n
i=1
\biggl(
n
i
\biggr)
[(q - 1)i - 1] is not a minimal
locating-dominating set, and hence, \lambda (\Gamma (\BbbV )) \leq
\sum n
i=1
\biggl(
n
i
\biggr)
[(q - 1)i - 1].
Theorem 2.1 is proved.
Since I(P3) = 2, therefore we have the following proposition.
Proposition 2.2. Let \BbbV be a vector space of dimension 2 over a field \BbbF of 2 elements, then
I(\Gamma (\BbbV )) = 2.
The following theorem gives the identifying number of \Gamma (\BbbV ).
Theorem 2.2. Let \BbbV be a finite vector space over a field \BbbF of 2 elements, then I(\Gamma (\BbbV )) = n.
Proof. For n \geq 3 and q = 2, by Theorem 2.1(a) and inequality (1), I(\Gamma (\BbbV ) \geq n. Note that T1
is an identifying code for \Gamma (\BbbV ) because for each vertex say u \in V (\Gamma (\BbbV )), N [u] \cap T1 is the set of
all those elements of T1 which have non-zero coefficients in the unique linear combination of basis
vectors for u. Thus, for any two distinct elements u, v \in V (\Gamma (\BbbV )), N [u] \cap T1 and N [v] \cap T1 are
distinct. Hence, I(\Gamma (\BbbV )) \leq n.
Theorem 2.2 is proved.
Let \BbbV be a finite vector space and q \geq 3, then \Gamma (\BbbV ) has twin sets Tik , 1 \leq i \leq n, 1 \leq k \leq
\biggl(
n
i
\biggr)
and each of these twin subset has adjacent twins, therefore identifying code for \Gamma (\BbbV ) does not exist.
Thus, we have the following remark.
Remark 2.2. Let \BbbV be a vector space of dimension n \geq 3 and q \geq 3, then identifying code for
\Gamma (\BbbV ) does not exist.
Lemma 2.4. Let \BbbV be a vector space of dimension n \geq 3 and q = 2, then T1 is the only
minimal identifying code for \Gamma (\BbbV ).
Proof. Suppose on contrary I \prime D be another minimal identifying code of \Gamma (\BbbV ), then there exist
at least one element say br \in T1 such that br \not \in I \prime D (because otherwise T1 \subset I \prime D ). Take two elements
ur \in Tn - 1 (using same notation as in proof of Lemma 2.3) and w \in Tn. Since N [w] = V (\Gamma (\BbbV ))
and N [ur] = V (\Gamma (\BbbV )) \setminus \{ br\} , therefore N [w] \cap I \prime D = N [ur] \cap I \prime D \not = \varnothing , a contradiction.
Lemma 2.4 is proved.
2.1. Exchange property. Locating-dominating sets are said to have the exchange property in
a graph \Gamma if for every two distinct minimal locating-dominating sets LD1 , LD2 and u1 \in LD1 ,
then there exists u2 \in LD2 so that (LD2 \setminus \{ u2\} ) \cup \{ u1\} is also a minimal locating-dominating
set. If locating-dominating sets has the exchange property in a graph \Gamma , then all minimal locating-
dominating sets of \Gamma has same number of elements. To show that the exchange property does not
hold in a graph, it is sufficient to show that there exist two minimal locating-dominating sets of
different cardinalities. However, the condition is not necessary.
Lemma 2.5. For q = 2 and n > 3, the exchange property does not hold for locating-dominating
sets in graph \Gamma (\BbbV ).
Proof. For n = 4, the exchange property does not hold because T1 and \{ b1 + b4, b2 + b4, b3 +
+ b4\} \cup T3 are minimal locating-dominating sets of different cardinalities.
For n \geq 5, T1 and T2\cup Tn - 1 are two locating-dominating sets of cardinalities n and
\biggl(
n
2
\biggr)
+n by
Lemma 2.2. For notational convenience, we use A = T2 \cup Tn - 1. We will prove that A is a minimal
locating-dominating set of \Gamma (\BbbV ). Let u \in A and w \in Tn. There are two possible cases for u.
1. If u \in T2, then u has exactly two non-zero coefficients in its unique linear combination
of basis vectors, say these vectors set as Bu. Choose an element in v \in Tn - 2 such that v has
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
958 M. MURTAZA, I. JAVAID, M. FAZIL
exactly n - 2 non-zero coefficients in the unique linear combination of basis vectors in B \setminus Bu. Then
N(v) \cap A \setminus \{ u\} = N(w) \cap A \setminus \{ u\} . Thus, A \setminus \{ u\} is not locating-dominating set.
2. If u \in Tn - 1, then N(u) \cap A \setminus \{ u\} = N(w) \cap A \setminus \{ u\} . Thus, T2 \cup Tn - 1 is a minimal
locating-dominating set. Hence, exchange property does not hold for locating-dominating sets in
graph \Gamma (\BbbV ).
Lemma 2.5 is proved.
In the proof of the following lemma, we use the same notation Tik for the kth twin set of class
Ti as we have used in the proof of Theorem 2.1(b).
Lemma 2.6. For q \geq 3, the exchange property holds for locating-dominating sets in graph
\Gamma (\BbbV ).
Proof. Since there are (q - 1)i choices for removing one vertex from a twin set Tik of cardinality
(q - 1)i, therefore there are
\prod n
i=1
\biggl(
n
i
\biggr)
(q - 1)i minimal locating-dominating sets in \Gamma (\BbbV ). Let
LD1 \not = LD2 be two such minimal locating-dominating sets. Let u1 \in LD1 , we further assume
that u1 \not \in LD2 (for otherwise (LD2 \setminus \{ u1\} ) \cup \{ u1\} is obviously a minimal locating-dominating
set of \Gamma (\BbbV ). Also, u1 \in Tik for some i, 1 \leq i \leq n, and some k, 1 \leq k \leq
\biggl(
n
i
\biggr)
. Since u1 \in
\in \{ LD1 \cap Tik\} \setminus \{ LD2 \cap Tik\} and LD1 , LD2 are minimal, therefore there exists an element u2 \in
\in \{ LD2 \cap Tik\} \setminus \{ LD1 \cap Tik\} . Since both u1 and u2 belong to the same twin set Tik , therefore
by Proposition 1.1 (LD2 \setminus \{ u2\} ) \cup \{ u1\} is a minimal locating-dominating set of \Gamma (\BbbV ). Hence, the
exchange property holds in \Gamma (\BbbV ).
Lemma 2.6 is proved.
From Lemma 2.4 we have the following remark.
Remark 2.3. Let \BbbV be a vector space of dimension n \geq 3 and q = 2, then identifying code
have the exchange property in \Gamma (\BbbV ).
From Lemma 2.5 we have the following remark.
Remark 2.4. In general, the locating-dominating sets does not have the exchange property for
all graphs.
References
1. D. F. Anderson, P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217, 434 – 447 (1999).
2. C. Bates, D. Bondy, S. Perkins, P. Rowley, Commuting involution graphs for symmetric groups, J. Algebra, 266,
133 – 153 (2003).
3. I. Beck, Coloring of commutative rings, J. Algebra, 116, 208 – 226 (1988).
4. T. Y. Berger-Wolf, W. E. Hart, J. Saia, Discrete sensor placement problems in distribution networks, Math. and
Comput. Model., 42, № 13, 1385 – 1396 (2005).
5. N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, Eur.
J. Combin., 25, 969 – 987 (2004).
6. D. Bondy, The connectivity of commuting graphs, J. Combin. Theory, Ser. A, 113, 995 – 1007 (2006).
7. J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, Locating dominating codes, Appl. Math. and Comput.,
220, 38 – 45 (2013).
8. P. J. Cameron, S. Ghosh, The power graph of a finite group, Discrete Math., 311, 1220 – 1222 (2011).
9. H. M. de Carvalho, C. H. C. Little, Vector spaces and the Petersen graph, Electron. J. Combin., 15 (2008).
10. I. Chakrabarty, S. Ghosh, M. K. Sen, Undirected power graphs of semi group, Semigroup Forum, 78, 410 – 426
(2009).
11. I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes: NP-completeness results for directed
graphs, IEEE Trans. Inform. Theory, 48, 2192 – 2200 (2002).
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
COVERING CODES OF A GRAPH ASSOCIATED TO A FINITE VECTOR SPACE 959
12. I. Charon, O. Hudry, A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is
NP-hard, Theor. Comput. Sci., 290, 2109 – 2120 (2003).
13. W. Chen, On vector spaces associated with a graph, SIAM J. Appl. Math., 20, 526 – 529 (1971).
14. C. J. Colbourn, P. J. Slater, L. K. Stewart, Locating-dominating sets in series parallel networks, Congr. Numer., 56,
135 – 162 (1987).
15. A. Das, Non-zero component graph of a finite dimensional vector space, Commun. Algebra, 44, 3918 – 3926 (2016).
16. A. Das, On non-zero component graph of vector spaces over finite fields, J. Algebra and Appl., 16, № 1 (2016).
17. A. Finbow, B. L. Hartnell, On locating-dominating sets and well-covered graphs, Congr. Numer., 56, 135 – 162
(1987).
18. R. Gould, Graphs and vector spaces, Stud. Appl. Math., 37, 193 – 214 (1958).
19. C. Hernando, M. Mora, I. M. Pelaya, C. Seara, D. R. Wood, Extremal graph theory for metric dimension and
diameter, Electron. Notes Discrete Math., 29, 339 – 343 (2007).
20. I. Honkala, T. Laihonen, S. Ranto, On locating-dominating codes in binary Hamming spaces, Disc. Math. Theor.
Comput. Sci., 6, 265 – 282 (2004).
21. A. Iranmanesh, A. Jafarzadeh, On the commuting graph associated with symmetric and alternating groups, J. Algebra
and Appl., 7, 129 – 146 (2008).
22. N. Jafari Rad, S. H. Jafari, Results on the intersection graphs of subspaces of a vector space, available at
http://arxiv.org/abs/1105.0803v1.
23. M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE
Trans. Inform. Theory, 44, 599 – 611 (1998).
24. M. Laifenfeld, A. Trachtenberg, R. Cohen, D. Starobinski, Joint monitoring and routing in wireless sensor networks
using robust identifying codes, Proc. IEEE Broadnets 2007, 9, 197 – 206 (2007).
25. V. Manjula, Vector space of a graph, Int. J. Math. and Comput. Res., 2, 2320 – 7167 (2014).
26. A. R. Moghaddamfar, S. Rahbariyan, W. J. Shi, Certain properties of the power graph associated with a finite group,
J. Algebra and Appl., 13, № 7 (2014).
27. R. Nikandish, H. R. Maimani, A. Khaksari, Coloring of a non-zero component graph associated with a finite
dimensional vector space, J. Algebra and Appl., 16, № 09 (2017).
28. D. F. Rall, P. J. Slater, On location-domination numbers for certian classes of graphs, Congr. Numer., 45, 97 – 106
(1984).
29. P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22, 445 – 455 (1988).
30. P. J. Slater, Fault-tolerant locating-dominating sets, Discrete Math., 249, 179 – 189 (2002).
31. P. J. Slater, Dominating and location in acyclic in graphs, Networks, 17, 55 – 64 (1987).
32. Y. Talebi, M. S. Esmaeilifar, S. Azizpour, A kind of intersection graph of vector space, J. Discrete Math. Sci. and
Cryptogr., 12, № 6, 681 – 689 (2009).
33. H. Benish, I. Javaid, M. Murtaza, Automorphism related parameters of a graph associated to a finite vector space,
Util. Math., 111, № Jun, 35 – 48 (2019).
34. M. Murtaza, M. Fazil, I. Javaid, Locating-dominating sets of functigraphs, Theor. Comput. Sci., 799, 115 – 123
(2019).
Received 15.05.17
ISSN 1027-3190. Укр. мат. журн., 2020, т. 72, № 7
|
| id | umjimathkievua-article-652 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-03-24T02:03:34Z |
| publishDate | 2020 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/18/939274f2623380808161601e86060d18.pdf |
| spelling | umjimathkievua-article-6522022-03-26T11:01:53Z Covering codes of a graph associated to a finite vector space Covering codes of a graph associated to a finite vector space Murtaza, M. Javaid, I. Fazil , M. Murtaza, M. Javaid, I. Fazil , M. UDC 512.5 In this paper, we investigate the problem of covering the vertices of a graph associated to a finite vector space as introduced by Das [Commun. Algebra, 44, 3918 – 3926 (2016)], such that we can uniquely identify any vertex by examining the vertices that cover it. We use locating-dominating sets and identifying codes, which are closely related concepts for this purpose. We find the location-domination number and the identifying number of the graph and study the exchange property for locating-dominating sets and identifying codes. УДК 512.5 Коди покриття графа, що пов’язаний зi скiнченним векторним простором Дослiджується задача покриття вершин графа, що пов’язаний iз скiнченним векторним простором, як це визначено у [A. Das, Commun. Algebra, 44, 3918 – 3926 (2016)], так що ми можемо однозначно iдентифiкувати будь-яку вершинуза вершинами, що її накривають. У цiй роботi використовуються множини локацiї–домiнацiї, а також iдентифiкацiйнi коди, якi у даному випадку є дуже близькими поняттями. Знайденi числа локацiї–домiнацiї та iдентифiкацiйне число для графа, та вивчена властивiсть обмiну для множин локацiї–домiнацiї та iдентифiкацiйних кодiв. Institute of Mathematics, NAS of Ukraine 2020-07-15 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/652 10.37863/umzh.v72i7.652 Ukrains’kyi Matematychnyi Zhurnal; Vol. 72 No. 7 (2020); 952-959 Український математичний журнал; Том 72 № 7 (2020); 952-959 1027-3190 en https://umj.imath.kiev.ua/index.php/umj/article/view/652/8731 |
| spellingShingle | Murtaza, M. Javaid, I. Fazil , M. Murtaza, M. Javaid, I. Fazil , M. Covering codes of a graph associated to a finite vector space |
| title | Covering codes of a graph associated to a finite vector space |
| title_alt | Covering codes of a graph associated to a finite vector space |
| title_full | Covering codes of a graph associated to a finite vector space |
| title_fullStr | Covering codes of a graph associated to a finite vector space |
| title_full_unstemmed | Covering codes of a graph associated to a finite vector space |
| title_short | Covering codes of a graph associated to a finite vector space |
| title_sort | covering codes of a graph associated to a finite vector space |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/652 |
| work_keys_str_mv | AT murtazam coveringcodesofagraphassociatedtoafinitevectorspace AT javaidi coveringcodesofagraphassociatedtoafinitevectorspace AT fazilm coveringcodesofagraphassociatedtoafinitevectorspace AT murtazam coveringcodesofagraphassociatedtoafinitevectorspace AT javaidi coveringcodesofagraphassociatedtoafinitevectorspace AT fazilm coveringcodesofagraphassociatedtoafinitevectorspace |