Scholarlink

<p>This paper examines the relationship between perfect codes and Ramanujan graphs, with an emphasis on explicit constructions. We establish the existence of infinite families of <i>k</i>-regular Ramanujan graphs that admit perfect codes, as well as infinite families that admit total perfect codes. In contrast, we prove that the classical Lubotzky–Phillips–Sarnak (LPS) Ramanujan graphs of degree <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(p+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, where <i>p</i> is prime, admit neither perfect codes nor total perfect codes. These results provide a clear structural distinction between different explicit families of Ramanujan graphs. Furthermore, we demonstrate that LPS graphs cannot be realized via the Ramanujan <i>r</i>-covering method, thereby revealing intrinsic constraints of covering constructions and elucidating the distinctive position of LPS graphs within the general theory of expander graphs.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On graph-based codes over Ramanujan graphs: existence and design of infinite families

  • 期刊论文

  • 发表日期：

    2026年3月27日

查看全文
  • Annayat Ali,
  • Sihem Mesnager,
  • Rameez Raja

摘要

This paper examines the relationship between perfect codes and Ramanujan graphs, with an emphasis on explicit constructions. We establish the existence of infinite families of k-regular Ramanujan graphs that admit perfect codes, as well as infinite families that admit total perfect codes. In contrast, we prove that the classical Lubotzky–Phillips–Sarnak (LPS) Ramanujan graphs of degree \(p+1\) p + 1 , where p is prime, admit neither perfect codes nor total perfect codes. These results provide a clear structural distinction between different explicit families of Ramanujan graphs. Furthermore, we demonstrate that LPS graphs cannot be realized via the Ramanujan r-covering method, thereby revealing intrinsic constraints of covering constructions and elucidating the distinctive position of LPS graphs within the general theory of expander graphs.