Scholarlink

<p>We initiate a study of the vertex clique covering numbers of Johnson graphs <i>J</i>(<i>N</i>,&#xa0;<i>k</i>), the smallest numbers of cliques necessary to cover the vertices of those graphs. We prove identities for the values of these numbers when <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1663_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \le 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≤</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10623_2025_1663_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="78" /> </InlineMediaObject> <EquationSource Format="TEX">\(k \ge N - 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mi>N</mi> <mo>-</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, and using computational methods, we provide explicit values for a range of small graphs. By drawing on connections to coding theory and combinatorial design theory, we prove various bounds on the clique covering numbers for general Johnson graphs, and we show how constant-weight lexicodes can be utilized to create optimal covers of <i>J</i>(2<i>k</i>,&#xa0;<i>k</i>) when <i>k</i> is a small power of two.</p>

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

On the clique covering numbers of Johnson graphs

  • 期刊论文

  • 发表日期：

    2025年6月5日

查看全文
  • Søren Fuglede Jørgensen

摘要

We initiate a study of the vertex clique covering numbers of Johnson graphs J(N, k), the smallest numbers of cliques necessary to cover the vertices of those graphs. We prove identities for the values of these numbers when \(k \le 3\) k ≤ 3 , and \(k \ge N - 3\) k ≥ N - 3 , and using computational methods, we provide explicit values for a range of small graphs. By drawing on connections to coding theory and combinatorial design theory, we prove various bounds on the clique covering numbers for general Johnson graphs, and we show how constant-weight lexicodes can be utilized to create optimal covers of J(2k, k) when k is a small power of two.