Abstract:
The Star graph Sn is the Cayley graph of the symmetric group Symn with the generating set {(1i):2≤i≤n}. Arumugam and Kala proved that {π∈Symn:π(1)=1} is a perfect code in Sn for any n, n≥3. In this note we show that for any n, n≥6 the Star graph Sn contains a perfect code which is the union of cosets of the embedding of PGL(2,5) into Sym6.
Keywords:
perfect code, efficient dominating set, Cayley graph, Star graph, projective linear group, symmetric group.