EUVIMEDEUVIMED entdecken
Crossref

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

Ville Junnila, Tero Laihonen, Havu Miikonen

Discrete Mathematics & Theoretical Computer Science · 01.05.2026 · vol. 28:2 (Graph Theory)

DOI: 10.46298/dmtcs.16459 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 01.05.2026. Verfasst von Ville Junnila und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 \emph{min-forced vertices}. We show that the number of min-forced vertices in a connected nontrivial graph of order $n$ is bounded above by $\frac{2}{3}\left(n -γ^{LD}(G)\right)$, 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 $\frac{2}{5}$. Moreover, both of these bounds can be attained. In particular, the ratio $\frac{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. 22 pages, 6 figures

Zitieren

APA

Junnila, V., Laihonen, T., & Miikonen, H. (2026). New Results on Vertices that Belong to Every Minimum Locating-Dominating Code. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Graph Theory). https://doi.org/10.46298/dmtcs.16459

Vancouver

Junnila V, Laihonen T, Miikonen H. New Results on Vertices that Belong to Every Minimum Locating-Dominating Code. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Graph Theory). doi:10.46298/dmtcs.16459

BibTeX
@article{Junnila2026,
  author = {Junnila, Ville and Laihonen, Tero and Miikonen, Havu},
  title = {New Results on Vertices that Belong to Every Minimum Locating-Dominating Code},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:2},
  number = {Graph Theory},
  doi = {10.46298/dmtcs.16459}
}
Kostenlos starten →