Article in volume
Authors:
Title:
Identifying codes in the direct product of a path and a complete graph
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 463-486
Received: 2020-02-10 , Revised: 2020-11-05 , Accepted: 2020-11-05 , Available online: 2020-12-03 , https://doi.org/10.7151/dmgt.2380
Abstract:
Let $G$ be a simple, undirected graph with vertex set $V$. For any vertex
$v \in V$, the set $N[v]$ is the vertex $v$ and all its neighbors. A subset
$D \subseteq V(G)$ is a dominating set of $G$ if for every $v \in V(G)$,
$N[v] \cap D \neq \emptyset$. And a subset $F \subseteq V(G)$ is a separating
set of $G$ if for every distinct pair $u, v\in V(G)$, $N[u]\cap F \neq N[v]
\cap F$. An identifying code of $G$ is a subset $C \subseteq V(G)$ that is
dominating as well as separating. The minimum cardinality of an identifying
code in a graph $G$ is denoted by $\gamma^{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 $\gamma^{ID}(P_n × K_m)$ for $n\geq 3$, and
$m\geq 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
References:
- 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 - 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 - 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 - N. Bertrand, I. Charon, O. Hudry and A. Lobstein, $1$-identifying codes on trees, Australas. J. Combin. 31 (2005) 21–35.
- 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 - 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.
- 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 - 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 - F. Foucaud, Identifying codes in special graph classes (Master's Thesis, Universite Bordeaux, 2009).
- 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 - W. Goddard and K. Wash, ID codes in Cartesian products of cliques, J. Combin. Math. Combin. Comput. 85 (2013) 97–106.
- 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 - 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 - 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 - 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 - 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 - 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 - 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 - J.L. Kim and S.J. Kim, Identifying codes in q-ary hypercubes, Bull. Inst. Combin. Appl. 59 (2010) 93–102.
- 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 - T. Laihonen and J. Moncel, On graphs admitting codes identifying sets of vertices, Australas. J. Combin. 41 (2008) 81–91.
- A. Lobstein, Watching Systems, Identifying, Locating-Dominating and Discriminating Codes in Graphs (2014).
http://www.infres.enst.fr/lobstein/debutBIBidetlocdom - 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 - 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 - 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 - 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 - D. West, Introduction to Graph Theory (Prentice Hall of India, 2002).
- 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
Close