Perfect codes in circulant graphs
2017
A perfect code in a graph =(V,E) is a subset C of V that is an independent set such that every vertex in VC is adjacent to exactly one vertex in C. A total perfect code in is a subset C of V such that every vertex of V is adjacent to exactly one vertex in C. A perfect code in the Hamming graph H(n,q) agrees with a q-ary perfect 1-code of length n in the classical setting. In this paper we give a necessary and sufficient condition for a circulant graph of degree p1 to admit a perfect code, where p is an odd prime. We also obtain a necessary and sufficient condition for a circulant graph of order n and degree pl1 to have a perfect code, where p is a prime and pl the largest power of p dividing n. Similar results for total perfect codes are also obtained in the paper.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
25
References
18
Citations
NaN
KQI