Covering codes of a graph associated to a finite vector space
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.
D. F. Anderson, P. S. Livingston, The zero-divisor graph of a commutative ring, J. Algebra, 217, 434 – 447 (1999), https://doi.org/10.1006/jabr.1998.7840
C. Bates, D. Bondy, S. Perkins, P. Rowley, Commuting involution graphs for symmetric groups, J. Algebra, 266, 133 – 153 (2003), https://doi.org/10.1016/S0021-8693(03)00302-8
I. Beck, Coloring of commutative rings, J. Algebra, 116, 208 – 226 (1988), https://doi.org/10.1016/0021-8693(88)90202-5
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), https://doi.org/10.1016/j.mcm.2005.03.005
N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, Eur. J. Combin., 25, 969 – 987 (2004), https://doi.org/10.1016/j.ejc.2003.12.013
D. Bondy, The connectivity of commuting graphs, J. Combin. Theory, Ser. A, 113, 995 – 1007 (2006),https://doi.org/10.1016/j.jcta.2005.09.003
J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas, Locating dominating codes, Appl. Math. and Comput., 220, 38 – 45 (2013), https://doi.org/10.1016/j.amc.2013.05.060
P. J. Cameron, S. Ghosh, The power graph of a finite group, Discrete. Math., 311, 1220 – 1222 (2011), https://doi.org/10.1016/j.disc.2010.02.011
D. Carvalho, H. Marcelo, C. H. C. Little, Vector spaces and the Petersen graph, Electron. J. Combin., 15.1, (2008), no. 1, Research Paper 9, 13 pp., http://www.combinatorics.org/Volume_15/Abstracts/v15i1r9.html
I. Chakrabarty, S. Ghosh, M. K. Sen, Undirected power graphs of semi group, Semigroup Forum, 78, 410 – 426 (2009), https://doi.org/10.1007/s00233-008-9132-y
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), https://doi.org/10.1109/TIT.2002.800490
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), https://doi.org/10.1016/S0304-3975(02)00536-4
W. Chen, On vector spaces associated with a graph, SIAM J. Appl. Math., 20, 526 – 529 (1971), https://doi.org/10.1137/0120054
C. J. Colbourn, P. J. Slater, L. K. Stewart, Locating-dominating sets in series parallel networks, Congr. Numer., 56, 135 – 162 (1987), https://doi.org/10.1016/j.disc.2015.11.016
A. Das, Non-zero component graph of a finite dimensional vector space, Commun. Algebra, 44, 3918 – 3926 (2016), https://doi.org/10.1080/00927872.2015.1065866
A. Das, On non-zero component graph of vector spaces over finite fields, J. Algebra and Appl., 16, №. 1 (2016), https://doi.org/10.1142/S0219498817500074
A. Finbow, B. L. Hartnell, On locating-dominating sets and well-covered graphs, Congr. Numer., 56, 135 – 162 (1987), https://doi.org/10.1016/S0012-365X(03)00297-8
R. Gould, Graphs and vector spaces, Stud. Appl. Math., 37, 193 – 214 (1958), https://doi.org/10.1002/sapm1958371193
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), https://doi.org/10.1016/j.endm.2007.07.058
I. Honkala, T. Laihonen, S. Ranto, On locating-dominating codes in binary Hamming spaces, Disc. Math. Theor. Comput. Sci., 6, 265 – 282 (2004), https://www.emis.de/journals/DMTCS/pdfpapers/dm060207.pdf
A. Iranmanesh, A. Jafarzadeh, On the commuting graph associated with symmetric and alternating groups, J. Algebra and Appl., 7, 129 – 146 (2008), https://doi.org/10.1142/S0219498808002710
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.
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), https://doi.org/10.1109/18.661507
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).
V. Manjula, Vector space of a graph, Int. J. Math. and Comput. Res., 2, 2320 – 7167 (2014).
A. R. Moghaddamfar, S. Rahbariyan, W. J. Shi, Certain properties of the power graph associated with finit group, J. Algebra and Appl., 13, 450040 (2014), https://doi.org/10.1142/S0219498814500406
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, No. 09, 1750173 (2017), https://doi.org/10.1142/S0219498817501730
D. F. Rall, P. J. Slater, On location-domination numbers for certian classes of graphs, Congr. Numer., 45, 97 – 106 (1984)
P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci., 22, 445 – 455 (1988)
P. J. Slater, Fault-tolerant locating-dominating sets, Discrete. Math., 249, 179 – 189 (2002), https://doi.org/10.1016/S0012-365X(01)00244-8
P. J. Slater, Dominating and location in acyclic in graphs, Networks, 17, 55 – 64 (1987), https://doi.org/10.1002/net.3230170105
Y. Talebi, M. S. Esmaeilifar, S. Azizpour, A kind of intersection graph of vector space, J. Discrete Math. Sci. and Cryptogr. 12, 6, №. 6, 681 – 689 (2009), https://doi.org/10.1080/09720529.2009.10698264
This work is licensed under a Creative Commons Attribution 4.0 International License.