On minimum identifying codes in some Cartesian product graphs

DOI10.1007/S00373-017-1813-4MaRDI QIDQ2409538zbMATH OpenOpenAlexFDO

Authors Douglas F. Rall, Kirsti Wash

Publication date 11 October 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.04089

zbMATH Keywords

Cartesian productdominating setgrid graphsidentifying codeprism

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: 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 $GBox{K}_2$. In particular, we show that $gid(GBox{K}_2)gegid(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(GBox{K}_2)$.

Recommendations

• ID codes in Cartesian products of cliques
• Identifying codes of the direct product of two cliques
• On graphs admitting codes identifying sets of vertices
• Identifying codes in the direct product of a complete graph and some special graphs
• Identifying codes in some subgraphs of the square lattice

Cites work

• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Extremal graphs for the identifying code problem
• Handbook of product graphs
• scientific article; zbMATH DE number 1436153 (Why is no real title available?)
• ID codes in Cartesian products of cliques
• Identifying codes of Cartesian product of two cliques of the same size
• Identifying codes of the direct product of two cliques
• Monotonicity of the minimum cardinality of an identifying code in the hypercube
• On a new class of codes for identifying vertices in graphs
• On dominating the Cartesian product of a graph and K₂
• On identifying codes in binary Hamming spaces
• On identifying codes in the Cartesian product of a path and a complete graph
• On Identifying Codes in the Triangular and Square Grids
• On the covering of vertices for fault diagnosis in hypercubes
• On the size of identifying codes in binary hypercubes
• The domination number of grids
• Topics in graph theory. Graphs and their Cartesian product

Cited in

(14)

• Identifying codes of Cartesian product of two cliques of the same size
• On a conjecture regarding identification in Hamming graphs
• Identifying codes in the complementary prism of cycles
• Optimal identifying codes of two families of Cayley graphs
• Improved upper bounds for identifying codes in n-dimensional q-ary cubes
• The general position number of Cartesian products involving a factor with small diameter
• Identifying codes of the direct product of two cliques
• Identifying codes of corona product graphs
• On identifying codes in the Cartesian product of a path and a complete graph
• A comparison of approaches for finding minimum identifying codes on graphs
• On graphs admitting codes identifying sets of vertices
• ID codes in Cartesian products of cliques
• On identifying codes in complementary prisms
• Identifying codes in the direct product of a path and a complete graph

This page was built for publication: On minimum identifying codes in some Cartesian product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409538)