Efficient Enumeration of Cliques in Graphs with Bounded Maximum Degree
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915707620425728 |
|---|---|
| author | Gong, Shi-Cai Wang, Jia-Jin Zhu, Xin-Hao Yuan, Bo-Jun |
| author_facet | Gong, Shi-Cai Wang, Jia-Jin Zhu, Xin-Hao Yuan, Bo-Jun |
| contents | 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. Building on this, Cutler and Radcliffe extended the result by identifying the graph that maximizes the number of cliques among graphs with bounded 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 and the Kahn-Zhao theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_01434 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Efficient Enumeration of Cliques in Graphs with Bounded Maximum Degree Gong, Shi-Cai Wang, Jia-Jin Zhu, Xin-Hao Yuan, Bo-Jun Combinatorics 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. Building on this, Cutler and Radcliffe extended the result by identifying the graph that maximizes the number of cliques among graphs with bounded 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 and the Kahn-Zhao theorem. |
| title | Efficient Enumeration of Cliques in Graphs with Bounded Maximum Degree |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2601.01434 |