Geodesic
Identifying codes in the direct product of a path and a complete graph
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 463-486 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

Let G be a simple, undirected graph with vertex set V. For any vertex v ∈ V, the set N[v] is the vertex v and all its neighbors. A subset D ⊆ V(G) is a dominating set of G if for every v ∈ V(G), N[v] ∩ D ∅. And a subset F ⊆ V(G) is a separating set of G if for every distinct pair u, v∈ V(G), N[u]∩ F N[v] ∩ F. An identifying code of G is a subset C ⊆ V(G) that is dominating as well as separating. The minimum cardinality of an identifying code in a graph G is denoted by γ^ID(G). The identifying codes of the direct product G_1 × G_2, where G_1 is a complete graph and G_2 is a complete/ regular/ complete bipartite graph, are known in the literature. In this paper, we find γ^ID(P_n × K_m) for n≥ 3, and m≥ 3 where P_n is a path of length n, and K_m is a complete graph on m vertices.
Keywords: identifying code, direct product, path, complete graph 
@article{DMGT_2023_43_2_a10,
     author = {Shinde, Neeta and Mane, Smruti and Waphare, Baloo},
     title = {Identifying codes in the direct product of a path and a complete graph},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {463--486},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/}
}
TY  - JOUR
AU  - Shinde, Neeta
AU  - Mane, Smruti
AU  - Waphare, Baloo
TI  - Identifying codes in the direct product of a path and a complete graph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 463
EP  - 486
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/
LA  - en
ID  - DMGT_2023_43_2_a10
ER  - 
%0 Journal Article
%A Shinde, Neeta
%A Mane, Smruti
%A Waphare, Baloo
%T Identifying codes in the direct product of a path and a complete graph
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 463-486
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/
%G en
%F DMGT_2023_43_2_a10
Shinde, Neeta; Mane, Smruti; Waphare, Baloo. Identifying codes in the direct product of a path and a complete graph. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 463-486. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a10/

[1] C. Balbuena, C. Dalfó and B. Martínez-Barona, Characterizing identifying codes from the spectrum of a graph or digraph, Linear Algebra Appl. 570 (2019) 138–147. https://doi.org/10.1016/j.laa.2019.02.010

[2] Y. Ben-Haim and S. Litsyn, Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math. 19 (2005) 69–82. https://doi.org/10.1137/S0895480104444089

[3] N. Bertrand, I. Charon, O. Hudry and A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European J. Combin. 25 (2004) 969–987. https://doi.org/10.1016/j.ejc.2003.12.013

[4] N. Bertrand, I. Charon, O. Hudry and A. Lobstein, 1-identifying codes on trees, Australas. J. Combin. 31 (2005) 21–35.

[5] C. Chen, C. Lu and Z. Miao, Identifying codes and locating-dominating sets on paths and cycles, Discrete Appl. Math. 159 (2011) 1540–1547. https://doi.org/10.1016/j.dam.2011.06.008

[6] G. Cohen, I. Honkala, M. Mollard, S. Gravier, A. Lobstein, C. Payan and G. Zémor, Improved identifying codes for the grid, Electron. J. Combin., Comments to Vol. 6 no. 1 (1999) #R19.

[7] M. Feng and K. Wang, Identifying codes of corona product graphs, Discrete Appl. Math. 169 (2014) 88–96. https://doi.org/10.1016/j.dam.2013.12.017

[8] M. Feng, M. Xu and K. Wang, Identifying codes of lexicographic product of graphs, Electron. J. Combin. 19 (2012) #P56. https://doi.org/10.37236/2974

[9] F. Foucaud, Identifying codes in special graph classes (Master's Thesis, Universite Bordeaux, 2009).

[10] F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud, On the size of identifying codes in triangle-free graphs, Discrete Appl. Math. 160 (2012) 1532–1546. https://doi.org/10.1016/j.dam.2012.02.009

[11] W. Goddard and K. Wash, ID codes in Cartesian products of cliques, J. Combin. Math. Combin. Comput. 85 (2013) 97–106.

[12] S. Gravier, J. Moncel and A. Semri, Identifying codes of cycles, European J. Combin. 27 (2006) 767–776. https://doi.org/10.1016/j.ejc.2004.09.005

[13] S. Gravier, J. Moncel and A. Semri, Identifying codes of Cartesian product of two cliques of the same size, Electron. J. Combin. 15 (2008) #N4. https://doi.org/10.37236/879

[14] J. Hedetniemi, On identifying codes in the Cartesian product of a path and a complete graph, J. Comb. Optim. 31 (2016) 1405–1416. https://doi.org/10.1007/s10878-015-9830-9

[15] I. Honkala and A. Lobstein, On identifying codes in binary Hamming spaces, J. Combin. Theory Ser. A 99 (2002) 232–243. https://doi.org/10.1006/jcta.2002.3263

[16] S. Janson and T. Laihonen, On the size of identifying codes in binary hypercubes, J. Combin. Theory Ser. A 116 (2009) 1087–1096. https://doi.org/10.1016/j.jcta.2009.02.004

[17] V. Junnila and T. Laihonen, Optimal identifying codes in cycles and paths, Graphs Combin. 28 (2012) 469–481. https://doi.org/10.1007/s00373-011-1058-6

[18] M.G. Karpovsky, K. Chakrabarty and L.B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (1998) 599–611. https://doi.org/10.1109/18.661507

[19] J.L. Kim and S.J. Kim, Identifying codes in q-ary hypercubes, Bull. Inst. Combin. Appl. 59 (2010) 93–102.

[20] M. Laifenfeld and A. Trachtenberg, Identifying codes and covering problems, IEEE Trans. Inform. Theory 54 (2008) 3929–3950. https://doi.org/10.1109/TIT.2008.928263

[21] T. Laihonen and J. Moncel, On graphs admitting codes identifying sets of vertices, Australas. J. Combin. 41 (2008) 81–91.

[22] A. Lobstein, \textrm{Watching Systems, Identifying, Locating-Dominating and Discriminating Codes in Graphs} (2014). http://www.infres.enst.fr/lobstein/debutBIBidetlocdom

[23] M. Lu, J. Xu and Y. Zhang, Identifying codes in the direct product of a complete graph and some special graphs, Discrete Appl. Math. 254 (2019) 175–182. https://doi.org/10.1016/j.dam.2018.06.027

[24] D.F. Rall and K. Wash, Identifying codes of the direct product of two cliques, European J. Combin. 36 (2014) 159–171. https://doi.org/10.1016/j.ejc.2013.07.002

[25] D.F. Rall and K. Wash, On minimum identifying codes in some Cartesian product graphs, Graphs Combin. 33 (2017) 1037–1053. https://doi.org/10.1007/s00373-017-1813-4

[26] P. M. Weichsel, The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 (1962) 47–52. https://doi.org/10.1090/S0002-9939-1962-0133816-6

[27] D. West, Introduction to Graph Theory (Prentice Hall of India, 2002).

[28] M. Xu, K. Thulasiraman and X.-D. Hu, Identifying codes of cycles with odd orders, European J. Combin. 29 (2008) 1717–1720. https://doi.org/10.1016/j.ejc.2007.09.006