A1 Refereed original research article in a scientific journal
New Results on Vertices that Belong to Every Minimum Locating-Dominating Code; 
Authors: Junnila, Ville; Laihonen, Tero; Miikonen, Havu
Publisher: Discrete Mathematics & Theoretical Computer Science
Publication year: 2026
Journal: Discrete Mathematics and Theoretical Computer Science
Article number: 20
Volume: 28
Issue: 2
ISSN: 1462-7264
eISSN: 1365-8050
DOI: https://doi.org/10.46298/dmtcs.16459
Publication's open availability at the time of reporting: Open Access
Publication channel's open availability : Open Access publication channel
Web address : https://doi.org/10.46298/dmtcs.16459
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/526553667
Self-archived copy's licence: CC BY
Self-archived copy's version: Publisher`s PDF
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.
Keywords:
Algorithmic complexity, Characterization, Forced vertex, number of different codes
Downloadable publication This is an electronic reprint of the original article. |
Funding information in the publication:
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.