×
Feng, Rongquan; Huang, He; Zhou, Sanming

Perfect codes in circulant graphs. (English) Zbl 1361.05129

Discrete Math. 340, No. 7, 1522-1527 (2017).
Summary: A perfect code in a graph \(\varGamma = (V, E)\) is a subset \(C\) of \(V\) that is an independent set such that every vertex in \(V \setminus C\) is adjacent to exactly one vertex in \(C\). A total perfect code in \(\varGamma\) 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 \(p - 1\) 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 \(p^l - 1\) to have a perfect code, where \(p\) is a prime and \(p^l\) the largest power of \(p\) dividing \(n\). Similar results for total perfect codes are also obtained in the paper.

Cited in 24 Documents

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
94B60 Other types of codes

Keywords:

perfect code; total perfect code; efficient dominating set; efficient open dominating set; Cayley graph; circulant graph
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Ahlswede, R.; Aydinian, H. K.; Khachatrian, L. H., On perfect codes and related concepts, Des. Codes Cryptogr., 22, 221-237 (2001) · Zbl 0971.94014
[2] Biggs, N., Perfect codes in graphs, J. Combin. Theory Ser. B, 15, 288-296 (1973) · Zbl 0256.94009
[3] Dejter, I. J.; Serra, O., Efficient dominating sets in Cayley graphs, Discrete Appl. Math., 129, 319-328 (2003) · Zbl 1035.05060
[4] Deng, Y.-P., Efficient dominating sets in circulant graphs with domination number prime, Inform. Process. Lett., 114, 700-702 (2014) · Zbl 1358.05212
[5] Deng, Y.-P.; Sun, Y.-Q.; Liu, Q.; Wang, H.-C., Efficient dominating sets in circulant graphs, Discrete Math., 340, 1503-1507 (2017) · Zbl 1361.05094
[6] Etienne, G., Perfect codes and regular partitions in graphs and groups, European J. Combin., 8, 139-144 (1987) · Zbl 0626.05051
[7] Etzion, T., Product constructions for perfect Lee codes, IEEE Trans. Inform. Theory, 57, 7473-7481 (2011) · Zbl 1365.94509
[8] Ghidewon, A.-A.; Hammack, R. H.; Taylor, D. T., Total perfect codes in tensor products of graphs, Ars Combin., 88, 129-134 (2008) · Zbl 1224.94058
[9] Heden, O., A survey of perfect codes, Adv. Math. Commun., 2, 223-247 (2008) · Zbl 1274.94151
[11] Jarvis, F., Algebraic Number Theory (2014), Springer · Zbl 1303.11001
[12] Knor, M.; Potočnik, P., Efficient domination in cubic vertex-transitive graphs, European J. Combin., 33, 8, 1755-1764 (2012) · Zbl 1248.05141
[13] Kratochvíl, J., Perfect codes over graphs, J. Combin. Theory Ser. B, 40, 224-228 (1986) · Zbl 0563.94017
[14] Lee, J., Independent perfect domination sets in Cayley graphs, J. Graph Theory, 37, 213-219 (2001) · Zbl 0996.05096
[15] Martínez, C.; Beivide, R.; Gabidulin, E., Perfect codes for metrics induced by circulant graphs, IEEE Trans. Inform. Theory, 53, 3042-3052 (2007) · Zbl 1325.94159
[16] Obradović, N.; Peters, J.; Ružić, G., Efficient domination in circulant graphs with two chord lengths, Inform. Process. Lett., 102, 253-258 (2007) · Zbl 1184.68046
[17] Reji Kumar, K.; MacGillivray, G., Efficient domination in circulant graphs, Discrete Math., 313, 767-771 (2013) · Zbl 1260.05115
[18] Terada, S., Perfect codes in \(SL(2, 2^f)\), European J. Combin., 25, 1077-1085 (2004) · Zbl 1055.05080
[19] van Lint, J. H., A survey of perfect codes, Rocky Mountain J. Math., 5, 199-224 (1975) · Zbl 0301.94007
[21] Zhou, S., Total perfect codes in Cayley graphs, Des. Codes Cryptogr., 81, 489-504 (2016) · Zbl 1347.05097
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.