Bounds on Identifying Codes in the Cartesian Product of a Star and a Path Graph
Abstract
In a graph, an identifying code (or ID code, for short) is a dominating set with the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. Thus every vertex can be uniquely identified by this intersection. The ID code number of a graph G is the minimum cardinality of an ID code of G and is denoted by γID(G). We present lower and upper bounds for γID in the Cartesian product of star and path graphs.
References
Auger, D. (2010). Minimal identifying codes in trees and planar graphs with large girth. European Journal of Combinatorics, 31:1372–1384.
Charon, I., Hudry, O., and Lobstein, A. (2003). Minimizing the size of an identifying or locating-dominating code in a graph is np-hard. Theoretical Computer Science, 290:2109–2120.
Cohen, G., Gravier, S., Honkala, I., Lobstein, A., Mollard, M., Payan, C., and Zémor, G. (1999). Improved identifying codes for the grid. Electronic Journal of Combinatorics, 6(1).
Goddard, W. and Wash, K. (2013). Id codes in cartesian products of cliques. Journal of Combinatorial Mathematics and Combinatorial Computing, 85:97–106.
Gravier, S., Moncel, J., and Semri, A. (2008). Identifying codes of cartesian product of two cliques of the same size. Electronic Journal of Combinatorics, 15(1).
Hedetniemi, J. (2016). On identifying codes in the cartesian product of a path and a complete graph. Journal of Combinatorial Optimization, 31:1405–1416.
Jean, D. (2023). Watching systems, identifying, locating-dominating and discriminating codes in graphs. Last accessed on: April 05, 2023.
Karpovsky, M. G., Chakrabarty, K., and Levitin, L. B. (1998). On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, IT-44:599–611.
Rall, D. F. and Wash, K. (2017). On minimum identifying codes in some cartesian product graphs. Graphs and Combinatorics, 33:1037–1053.
Charon, I., Hudry, O., and Lobstein, A. (2003). Minimizing the size of an identifying or locating-dominating code in a graph is np-hard. Theoretical Computer Science, 290:2109–2120.
Cohen, G., Gravier, S., Honkala, I., Lobstein, A., Mollard, M., Payan, C., and Zémor, G. (1999). Improved identifying codes for the grid. Electronic Journal of Combinatorics, 6(1).
Goddard, W. and Wash, K. (2013). Id codes in cartesian products of cliques. Journal of Combinatorial Mathematics and Combinatorial Computing, 85:97–106.
Gravier, S., Moncel, J., and Semri, A. (2008). Identifying codes of cartesian product of two cliques of the same size. Electronic Journal of Combinatorics, 15(1).
Hedetniemi, J. (2016). On identifying codes in the cartesian product of a path and a complete graph. Journal of Combinatorial Optimization, 31:1405–1416.
Jean, D. (2023). Watching systems, identifying, locating-dominating and discriminating codes in graphs. Last accessed on: April 05, 2023.
Karpovsky, M. G., Chakrabarty, K., and Levitin, L. B. (1998). On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, IT-44:599–611.
Rall, D. F. and Wash, K. (2017). On minimum identifying codes in some cartesian product graphs. Graphs and Combinatorics, 33:1037–1053.
Published
2023-08-06
How to Cite
FELIX, Juliana P.; CAPPELLE, Márcia R..
Bounds on Identifying Codes in the Cartesian Product of a Star and a Path Graph. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 55-59.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230607.
