{"id":"arxiv/2606.09733","url":"https://arxiv.org/abs/2606.09733","tags":["math.CO"],"score":0,"title":"On saturation problems involving clique number and matching number","domain":"math.CO","source":"arxiv","authors":["Zian Chen","Guorong Gao","Jianfeng Hou","Yue Ma"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-08","reactions":{}}