• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Locating-Dominating Codes in Cycles

Geoffrey Exoo, Ville Junnila, Tero Laihonen, Locating-Dominating Codes in Cycles. Australasian Journal of Combinatorics 49, 177–194, 2011.

Abstract:

The smallest cardinality of an $r$-locating-dominating code in a cycle $\C_n$ of length $n$ is denoted by $M_r^{LD}(\C_n)$. In this paper, we prove that for any $r \geq 5$ and $n \geq n_r$ when $n_r$ is large enough ($n_r=\mathcal{O}(r^3)$) we have $n/3 \leq M_r^{LD}(\C_n) \leq n/3+1$ if $n \equiv 3 \pmod{6}$ and $M_r^{LD}(\C_n) = \lceil n/3 \rceil$ otherwise. Moreover, we determine the exact values of $M_3^{LD}(\C_n)$ and $M_4^{LD}(\C_n)$ for all $n$.

BibTeX entry:

@ARTICLE{jExJuLa11a,
  title = {Locating-Dominating Codes in Cycles},
  author = {Exoo, Geoffrey and Junnila, Ville and Laihonen, Tero},
  journal = {Australasian Journal of Combinatorics},
  volume = {49},
  pages = {177–194},
  year = {2011},
  keywords = {Locating-dominating code; optimal code; domination; graph; cycle},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication