Characterization of subgroup perfect codes in Cayley graphs. (English) Zbl 1439.05104
A subset \(C\) of the vertex set of a graph \(G\) is called a perfect code in \(G\) if every vertex of \(G\) is at distance no more than 1 to exactly one vertex of \(C.\) A subset \(C\) of a group \(\Gamma\) is called a perfect code of \(\Gamma\) if \(C\) is a perfect code in some Cayley graph of \(\Gamma\). The perfect codes are also called efficient dominating sets or independent perfect dominating sets in pure graph theoretical terms. In this paper, the authors provide sufficient and necessary conditions for a subgroup \(\Omega\) of a finite group \(\Gamma\) to be a perfect code of \(\Gamma\). Based on this, they provide a characterization for of all finite groups that have no nontrivial subgroup as a perfect code.
Reviewer: T. Tamizh Chelvam (Tirunelveli)
MSC:
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
| 05C12 | Distance in graphs |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 94B60 | Other types of codes |
References:
| [1] | Burnside, W., Theory of Groups of Finite Order (1911), Cambridge University Press: Cambridge University Press Cambndge · JFM 42.0156.02 |
| [2] | Dejter, I. J.; Serra, O., Efficient dominating sets in Cayley graphs, Discrete Appl. Math., 129, 2-3, 319-328 (2003) · Zbl 1035.05060 |
| [3] | Deng, Y.-P., Efficient dominating sets in circulant graphs with domination number prime, Inform. Process. Lett., 114, 12, 700-702 (2014) · Zbl 1358.05212 |
| [4] | Deng, Y.-P.; Sun, Y.-Q.; Liu, Q.; Wang, H.-C., Efficient dominating sets in circulant graphs, Discrete Math., 340, 7, 1503-1507 (2017) · Zbl 1361.05094 |
| [5] | Feng, R.; Huang, H.; Zhou, S., Perfect codes in circulant graphs, Discrete Math., 340, 7, 1522-1527 (2017) · Zbl 1361.05129 |
| [6] | Huang, H.; Xia, B.; Zhou, S., Perfect codes in Cayley graphs, SIAM J. Discrete Math., 32, 1, 548-559 (2018) · Zbl 1381.05032 |
| [7] | Kratochvíl, J., Perfect codes over graphs, J. Combin. Theory Ser. B, 40, 2, 224-228 (1986) · Zbl 0563.94017 |
| [8] | Lee, J., Independent perfect domination sets in Cayley graphs, J. Graph Theory, 37, 4, 213-219 (2001) · Zbl 0996.05096 |
| [9] | X. Ma, G.L. Walls, K. Wang, S. Zhou, Subgroup perfect codes in Cayley graphs, https://arxiv.org/abs/1904.01858. · Zbl 1453.05045 |
| [10] | Obradović, N.; Peters, J.; Ružić, G., Efficient domination in circulant graphs with two chord lengths, Inform. Process. Lett., 102, 6, 253-258 (2007) · Zbl 1184.68046 |
| [11] | Reji Kumar, K.; MacGillivray, G., Efficient domination in circulant graphs, Discrete Math., 313, 6, 767-771 (2013) · Zbl 1260.05115 |
| [12] | Tamizh Chelvam, T.; Mutharasu, S., Subgroups as efficient dominating sets in Cayley graphs, Discrete Appl. Math., 161, 9, 1187-1190 (2013) · Zbl 1277.05130 |
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.
