Nonexistence of Efficient Dominating Sets in the Cayley Graphs Generated by Transposition Trees of Diameter 3

Abstract

Let $d,n$ be positive integers such that $d<n$, and let $X_n^d$ be a Cayley graph generated by a transposition tree of diameter $d$. It is known that every $X_n^d$ with $d<3$ splits into efficient dominating sets. The main result of this paper is that $X_n^3$ does not have efficient dominating sets.

15 pages, 5 figures, 3 tables

References in corpus (2)

• An efficient algorithm for the diameter of Cayley graphs generated by transposition trees
• Diameter of Cayley graphs of permutation groups generated by transposition trees