On saturation problems involving clique number and matching number

Zian Chen, Guorong Gao, Jianfeng Hou, Yue Ma

arXivarxiv/2606.09733Jun 8, 2026math.COscore 0

For a clique $K_r$, a graph is $K_r$-saturated if it contains no copy of $K_r$ and the addition of any edge from its complement creates a $K_r$. A classical result of Erdős-Hajnal-Moon and Zykov shows that the number of edges of an $n$-vertex $K_r$-saturated graph is at least $(r-2)n-\binom{r-1}{2}$. In this paper, we focus on the number of edges of the $K_r$-saturated graphs with a fixed matching number. Let $G$ be an $n$-vertex $K_r$-saturated graph with matching number $ν(G) = s$. For sufficiently large $n$, we prove that the number of edges \begin{equation*} e(G)\geq…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2606.09733
curl -X POST /api/v1/records/arxiv/2606.09733/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.09733/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'