Efficient dominating sets in Cayley graphs. (English) Zbl 1035.05060
An independent set \(C\) of vertices in a graph is called an efficient dominating set if each vertex not in \(C\) is adjacent to exactly one vertex in \(C\). Efficient dominating sets are also called perfect codes. An \(E\)-chain is a countable family of nested graphs, each of which has an efficient dominating set. The authors give a constructing tool to produce \(E\)-chains of Cayley graphs. Using this tool infinite families of \(E\)-chains of Cayley graphs on symmetric groups are constructed.
Reviewer: Ulrike Baumann (Dresden)
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
References:
| [1] | Akers, S. B.; Krishnamurthy, B., A group theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 555-565 (1989) · Zbl 0678.94026 |
| [2] | Arumugam, S.; Kala, R., Domination parameters of star graphs, Ars Combin., 44, 93-96 (1996) · Zbl 0889.05056 |
| [3] | Berge, C., Graphs and Hypergraphs (1976), North-Holland: North-Holland Amsterdam · Zbl 0483.05029 |
| [4] | Biggs, N., Perfect codes in graphs, J. Combin. Theory Ser. B, 15, 288-296 (1973) · Zbl 0256.94009 |
| [5] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 |
| [6] | Kompelmacher, V. L.; Liskovetz, V. A., Sequential generation of arrangements by means of a basis of transpositions, Cybernetics, 3, 362-366 (1975) |
| [7] | Kratochvı́l, J., Perfect codes of graphs, J. Combin. Theory Ser. B, 40, 224-228 (1986) · Zbl 0563.94017 |
| [8] | A. Rosa, J. Siran, S. Znam, The graph of all labellings of a connected graph is Hamiltonian, unpublished.; A. Rosa, J. Siran, S. Znam, The graph of all labellings of a connected graph is Hamiltonian, unpublished. |
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.
