DIMACS TR: 2000-07

Efficient Dominating Sets in Cayley Graphs

Author: Italo J. Dejter and Oriol Serra


An independent set $C$ of vertices in a graph is an efficient dominating set when each vertex not in $C$ is adjacent to exactly one vertex in $C$.

A countable family of nested graphs, each of which has at least one efficient dominating set, is produced for each real number in the unit interval [0,1].

These families range from star graphs, for which the efficient domination property was proved by Arumugam and Kala, to pancake graphs.

The families obtained are extended to partitions of the vertex sets into efficient dominating sets. Uniqueness holds for the given partitions whenever the countable family is not that of the star graphs.

For star graphs, all the possible ways in which such a partition occurs are established.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2000/2000-07.ps.gz
DIMACS Home Page