Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

# Identifying Codes in the Direct Product of a Path and a Complete Graph

###### Accepted: 05 Nov 2020
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

Let G be a simple, undirected graph with vertex set V. For any vertex vV, the set N[v] is the vertex v and all its neighbors. A subset DV (G) is a dominating set of G if for every vV (G), N[v] ∩ D ≠ ∅. And a subset FV (G) is a separating set of G if for every distinct pair u, vV (G), N[u] ∩ F ≠ N[v] ∩ F. An identifying code of G is a subset CV (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 G1 × G2, where G1 is a complete graph and G2 is a complete/regular/complete bipartite graph, are known in the literature. In this paper, we find γID(Pn × Km) for n ≥ 3, and m ≥ 3 where Pn is a path of length n, and Km is a complete graph on m vertices.

#### MSC 2010

[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. doi:10.1016/j.laa.2019.02.01010.1016/j.laa.2019.02.010Search in Google Scholar

[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. doi:10.1137/S089548010444408910.1137/S0895480104444089Search in Google Scholar

[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. doi:10.1016/j.ejc.2003.12.01310.1016/j.ejc.2003.12.013Search in Google Scholar

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

[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. doi:10.1016/j.dam.2011.06.00810.1016/j.dam.2011.06.008Search in Google Scholar

[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.10.37236/1451Search in Google Scholar

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

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

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

[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. doi:10.1016/j.dam.2012.02.00910.1016/j.dam.2012.02.009Search in Google Scholar

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

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

[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. doi:10.37236/87910.37236/879Search in Google Scholar

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

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

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

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

[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. doi:10.1109/18.66150710.1109/18.661507Search in Google Scholar

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

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

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

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

[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. doi:10.1016/j.dam.2018.06.02710.1016/j.dam.2018.06.027Search in Google Scholar

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

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

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

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

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

• #### A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD