Covering Codes of a Graph Associated with a Finite Vector Space
- PDF / 147,953 Bytes
- 10 Pages / 594 x 792 pts Page_size
- 77 Downloads / 155 Views
COVERING CODES OF A GRAPH ASSOCIATED WITH A FINITE VECTOR SPACE M. Murtaza,1 I. Javaid,2 and M. Fazil2
UDC 512.5
We study the problem of covering of the vertices of a graph associated with a finite vector space introduced by Das [Comm. Algebra, 44, 3918–3926 (2016)] such that any vertex can be uniquely identified by examining the vertices from the covering. For this purpose, we use the locating-dominating sets and the identifying codes, i.e., closely related concepts. We find the location-domination number and the identifying number of the graph and study the exchange property of locating-dominating sets and identifying codes.
1. Preliminaries The problem of association of the graphs with algebraic structures turned into an interesting research topic for several last decades. In this connection, see, e.g., commuting graphs for groups [2, 6, 21], power graphs for groups and semigroups [8, 10, 26], and the zero-divisor graph associated with a commutative ring [1, 3]. The association of graphs with vector spaces has a long history that can be traced back to 1958 (see Gould [18]). Later, Chen [13] studied vector spaces associated with graphs. Carvalho [9] investigated the vector space and the Petersen graph. Later, Manjula [25] used vector spaces and made it possible to apply the techniques of linear algebra for the analysis of the graphs. The intersection graphs assigned to the vector spaces were studied in [22, 32]. Das [15] introduced a new graph structure, which is called a nonzero component graph on finite-dimensional vector spaces. He showed that the graph is connected and found its domination and independence numbers [16]. He also characterized the maximal cliques in the graph and found the exact number of cliques for some particular cases [16]. Das also presented some results on the size, edge connectivity, and the chromatic number of the graph [16]. For more information about the nonzero component graph, see [27, 33]. The problem of covering code for a given graph involves the determination of the set of vertices with the minimum cardinality whose neighborhoods uniquely overlap at any given vertex of the graph. This problem revealed its fundamental nature through a great variety of applications. The locating-dominating sets were introduced by Slater [29, 31], while the identifying codes were proposed by Karpovsky, et al. [23]. The locating-dominating sets are quite similar to the identifying codes with a subtle difference that only the vertices that do not belong to the locating-dominating set are required to have unique identifying sets. The decision problem for the locatingdominating sets of directed graphs was shown to be an NP-complete problem [11]. A considerable literature was published in this field (see [5, 12, 14, 17, 20, 28–30, 34]). In [7], it was indicated that each locating-dominating set is both locating and dominating. However, a set, which is both locating and dominating, is not necessarily a locating-dominating set. The initial application of locating-dominating sets and identifying codes w
Data Loading...
