Efficient Dominating Sets in Cayley Graphs on Symmetric Groups

Yunping DENG

Department of Mathematics, Shanghai University of Electric Power, Shanghai, 200090, China

Abstract: For any given positive integers n and k with n > k, let (n,k ) { : {1,2, , } \ { }}

T = si iÎ L n k be a generating set of the symmetric group Sn of degree n , where each (n,k )

si ÎT satisfies that k i i,i i k, s = s = and each (n,k ) { } si ÎT  sn satisfies that n i n. s = The Cayley graph on Sn with respect to T(n,k ) is denoted by G(n,k ). In this paper, we determine the domination number of G(n,k) , and obtain some results about efficient dominating sets in G(n,k ).

Keywords: Symmetric group; Cayley graph; Efficient dominating set