New Results on Vertices that Belong to Every Minimum Locating-Dominating Code;




Junnila, Ville; Laihonen, Tero; Miikonen, Havu

PublisherDiscrete Mathematics & Theoretical Computer Science

2026

 Discrete Mathematics and Theoretical Computer Science

20

28

2

1462-7264

1365-8050

DOIhttps://doi.org/10.46298/dmtcs.16459

https://doi.org/10.46298/dmtcs.16459

https://research.utu.fi/converis/portal/detail/Publication/526553667



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. In particular, the ratio 2 5 is obtained by paths of order 5m having a unique minimum locating-dominating code of size 2m. Furthermore, as a natural extension, we determine the number of different minimum locating-dominating codes in paths of all orders. In addition, we show that deciding whether a vertex is min-forced is co-NP-hard.




Algorithmic complexityCharacterizationForced vertexnumber of different codes


The authors have been partially supported by Research Council of Finland grant number 338797. Havu Miikonen has been partially supported by the Turku University Foundation.


Last updated on 16/06/2026 08:04:09 AM