Identifying codes of cycles with odd orders. (English) Zbl 1145.94020
Summary: The problem of the \(r\)-identifying code of a cycle \(C_n\) has been solved totally when \(n\) is even. Recently, S. Gravier et al.
[Eur. J. Comb. 27, No. 5, 767–776 (2006; Zbl 1089.94045)] gave the \(r\)-identifying code for the cycle \(C_n\) with the minimum cardinality for odd \(n\), when \(n\geq 3r+2\) and \(\gcd(2r+1,n)\neq 1\). In this paper, we deal with the \(r\)-identifying code of the cycle \(C_n\) for odd \(n\), when \(n\geq 3r+2\) and \(\gcd(2r+1,n)=1\).
MSC:
| 94B15 | Cyclic codes |
Citations:
Zbl 1089.94045References:
| [1] | Bertrand, N.; Charon, I.; Hudry, O.; Lobstein, A., 1-Identifying codes on trees, Australasian Journal of Combinatorics, 31, 21-35 (2005) · Zbl 1081.94039 |
| [2] | Bertrand, N.; Charon, I.; Hudry, O.; Lobstein, A., Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics, 25, 969-987 (2004) · Zbl 1053.05095 |
| [3] | Charon, I.; Hudry, O.; Lobstein, A., Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard, Theoretical Computer Science, 290, 2109-2120 (2003) · Zbl 1044.68066 |
| [4] | Daniel, M., Codes identifiants, (Mémoire pour le DEA ROCO (June 2003), Université Joseph Fourier: Université Joseph Fourier Grenoble, France) |
| [5] | Daniel, M.; Gravier, S.; Moncel, J., Identifying codes in some subgraphs of the square lattice, Theoretical Computer Science, 319, 411-421 (2004) · Zbl 1047.94019 |
| [6] | Frieze, A.; Martin, R.; Moncel, J.; Ruszinkó, M.; Smyth, C., Codes identifying sets of vertices in random networks, Discrete Mathematics, 307, 1094-1107 (2007) · Zbl 1160.94021 |
| [7] | Gravier, S.; Moncel, J.; Semri, A., Identifying codes of cycles, European Journal of Combinatorics, 27, 767-776 (2006) · Zbl 1089.94045 |
| [8] | Karpovsky, M. G.; Chakrabarty, K.; Levitin, L. B., On a new class of codes for identifying vertices in graphs, IEEE Transaction on Information Theory, 44, 559-611 (1998) · Zbl 1105.94342 |
| [9] | Roberts, D. L.; Roberts, F. S., Locating sensors in paths and cycles: The case of 2-identifying codes, European Journal of Combinatorics, 29, 72-82 (2008) · Zbl 1233.94031 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
