初等交换群凯莱图的完备码与完全图的正则覆盖

Perfect Codes of Cayley Graphs of Elementary Abelian Groups and Regular Covering of Complete Graphs

LEE证明了超立方体图Qn存在完备码当且仅当n=2m-1(m≥2是自然数),当且仅当它是完全图Kn+1的正则覆盖.本文中,给出了这个结论的一个简单证明,并把这个结论推广到了初等交换群的凯莱图中.证明了初等交换p-群Zp^n(这里p是奇素数)的凯莱图有完备码当且仅当n=(p^m-1)/2(这里m是自然数且n≥2),当且仅当它是完全图K2n+1的正则覆盖.

LEE proved that Q n has a perfect code if and only if n=2 m- 1 for some integer m≥2, if and only if it is a regular covering of K n+1 .In this paper,we give a short simple proof of LEE’s result and generalize it to Cayley graphs of elementary Abelian groups.We show that a Cayley graph of an elementary Abelian p -group Zp^n has a perfect code if and only if n=(p^ m-1)/2 for some integer m and n≥2 , if and only if it is a regular covering of K2n+1 .