Covering codes of a graph associated to a finite vector space

M.  Murtaza; I.  Javaid; M.   Fazil

doi:10.37863/umzh.v72i7.652

M. Murtaza Centre Adv. Studies in Pure and Appl. Math., Bahauddin Zakariya Univ.,Multan, Pakistan https://orcid.org/0000-0002-1468-1316
I. Javaid Centre Adv. Studies in Pure and Appl. Math., Bahauddin Zakariya Univ.,Multan, Pakistan
M. Fazil Centre Adv. Studies in Pure and Appl. Math., Bahauddin Zakariya Univ.,Multan, Pakistan

DOI: https://doi.org/10.37863/umzh.v72i7.652

Abstract

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.

Author Biography

M. Fazil , Centre Adv. Studies in Pure and Appl. Math., Bahauddin Zakariya Univ.,Multan, Pakistan

References

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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: https://doi.org/10.37236/733

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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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). DOI: https://doi.org/10.1109/BROADNETS.2007.4550425

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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: https://doi.org/10.1080/09720529.2009.10698264