2025/09/01 by Junnila, Ville, Laihonen, Tero, Miikonen, Havu
#05C12 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2509.01473
Locating-dominating codes have been studied widely since their introduction in the 1980s by Slater and Rall. In this paper, we concentrate on vertices that must belong to all minimum locating-dominating codes in a graph. We call them min-forced vertices. We show that the number of min-forced vertices in a connected nontrivial graph of order n is bounded above by (2)/(3)(n -γLD(G)), where γLD(G) denotes the cardinality of a minimum locating-dominating code. This implies that the maximum ratio between the number of min-forced vertices and the order of a connected nontrivial graph is at most (2)/(5). Moreover, both of these bounds can be attained. We also determine the number of different minimum locating-dominating codes in all paths. In addition, we show that deciding whether a vertex is min-forced is co-NP-hard.