Scholarlink

<p>In recent years, there has been a surge of interest in extremal problems concerning the enumeration of independent sets or cliques in graphs with specific constraints. For instance, the Kahn–Zhao theorem establishes an upper bound on the number of independent sets in a <i>d</i>-regular graph; Cutler and Radcliffe identified the extremal graphs that maximize the number of cliques for a given order and maximum degree. In this paper, we introduce an innovative approach for counting cliques in graphs with a bounded maximum degree. To demonstrate the effectiveness of the method, we provide a new proof for the above Cutler–Radcliffe theorem.</p>

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

Efficient enumeration of cliques in graphs with bounded maximum degree

  • 期刊论文

  • 发表日期：

    2026年5月25日

查看全文
  • Shi-Cai Gong,
  • Jia-Jin Wang,
  • Xin-Hao Zhu,
  • Bo-Jun Yuan

摘要

In recent years, there has been a surge of interest in extremal problems concerning the enumeration of independent sets or cliques in graphs with specific constraints. For instance, the Kahn–Zhao theorem establishes an upper bound on the number of independent sets in a d-regular graph; Cutler and Radcliffe identified the extremal graphs that maximize the number of cliques for a given order and maximum degree. In this paper, we introduce an innovative approach for counting cliques in graphs with a bounded maximum degree. To demonstrate the effectiveness of the method, we provide a new proof for the above Cutler–Radcliffe theorem.