Efficient dominating sets in Cayley graphs

✍ Scribed by Italo J. Dejter; Oriol Serra

• Book ID: 104294127
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 506 KB
• Volume: 129
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(02)00573-5

✦ Synopsis

An independent set C of vertices in a graph is an e cient dominating set (or perfect code) when each vertex not in C is adjacent to exactly one vertex in C. An E-chain is a countable family of nested graphs, each of which has an e cient dominating set. The Hamming codes in the n-cubes provide a classical example of E-chains. We give a constructing tool to produce E-chains of Cayley graphs. This tool is used to construct inÿnite families of E-chains of Cayley graphs on symmetric groups. These families include the well-known star graphs, for which the e cient domination property was proved by Arumugam and Kala, and pancake graphs. Additional structural properties of the E-chains and the e cient dominating sets involved are also presented. Given a tree T , the T -graph associated to T seems to be a natural candidate of a graph with an e cient dominating set. However, we prove that a T -graph has an e cient dominating set if and only if T is a star.