2016/02/12 by Douglas F. Rall, Rall, Douglas F., Kirsti Wash +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1602.04089
arxiv created 2016/02/12 · arxiv updated 2016/02/15
An identifying code in a graph is a dominating set that also has the property that the closed neighborhood of each vertex in the graph has a distinct intersection with the set. The minimum cardinality of an identifying code, or ID code, in a graph G is called the ID code number of G and is denoted \gid(G). In this paper, we give upper and lower bounds for the ID code number of the prism of a graph, or G\Box K2. In particular, we show that \gid(G \Box K2) ≥ \gid(G) and we show that this bound is sharp. We also give upper and lower bounds for the ID code number of grid graphs and a general upper bound for \gid(G\Box K2).