Perfect \(r\)-Codes in Lexicographic Products of Graphs

Abstract

A perfect \(r\)-code in a graph is a subset of the graph’s vertices with the property that each vertex in the graph is within distance \(r\) of exactly one vertex in the subset. We determine the relationship between perfect \(r\)-codes in the lexicographic product of two simple graphs and perfect \(r\)-codes in each of the factors.