04-23【冯荣权】五教5106 吴文俊数学重点实验室组合图论系列讲座之168

发布者:万宏艳发布时间:2021-04-21浏览次数:75


报告题目:Perfect Codes in Cayley Graphs


报告人:冯荣权 (北京大学 教授)


报告时间:4月23号下午 3:00-3:45 


地点:五教5106


摘要:

A perfect code in a graph Γ = (V, E) is a subset C of V that is an independent set such that every vertex in V \ C is adjacent to exactly one vertex in C. A total perfect code in Γ is a subset C of V such that every vertex of V is adjacent to exactly one vertex in C. A perfect code in the Hamming graph H(n, q) agrees with a q-ary perfect 1-code of length n in the classical setting. In this talk we study perfect codes and total perfect codes in Cayley graphs, with a focus on when a subgroup of a given group is a perfect code or a total perfect code in a Cayley graph of the group. Furthermore, a necessary and sufficient condition for a circulant graph (a Cayley graph on cyclic groups) of degree p−1 (or degree p^l−1) to admit a perfect code is given in this talk, where p is a prime and p^l the largest power of p dividingn.