## DIMACS TR: 2000-07

## Efficient Dominating Sets in Cayley Graphs

### Author: Italo J. Dejter and Oriol Serra

**
ABSTRACT
**

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