A1 Refereed original research article in a scientific journal

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




AuthorsJunnila, Ville; Laihonen, Tero; Miikonen, Havu

PublisherDiscrete Mathematics & Theoretical Computer Science

Publication year2026

Journal: Discrete Mathematics and Theoretical Computer Science

Article number20

Volume28

Issue2

ISSN1462-7264

eISSN1365-8050

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

Publication's open availability at the time of reportingOpen Access

Publication channel's open availability Open Access publication channel

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

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/526553667

Self-archived copy's licenceCC BY

Self-archived copy's versionPublisher`s PDF


Abstract

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 complexityCharacterizationForced vertexnumber of different codes

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




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.


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