Journal article
Total perfect codes in Cayley graphs
S Zhou
Designs Codes and Cryptography | SPRINGER | Published : 2016
Abstract
A total perfect code in a graph Γ is a subset C of V(Γ) such that every vertex of Γ is adjacent to exactly one vertex in C. We give necessary and sufficient conditions for a conjugation-closed subset of a group to be a total perfect code in a Cayley graph of the group. As an application we show that a Cayley graph on an elementary abelian 2-group admits a total perfect code if and only if its degree is a power of 2. We also obtain necessary conditions for a Cayley graph of a group with connection set closed under conjugation to admit a total perfect code.
Grants
Awarded by Australian Research Council
Funding Acknowledgements
The author is grateful to three anonymous referees for their helpful comments which led to improvement of Theorem 5.5(b) and betterment of presentation of the paper. This research was supported by the Australian Research Council (FT110100629).