Saturation in Kneser Graphs

期刊论文
发表日期：

2024年8月1日

查看全文

S. V. Vakhrushev,
M. E. Zhukovskii,
A. Yu. Skorkin

摘要

Abstract

The Kneser graph \(\operatorname{KG}(n,2)\) is the graph whose vertices are pairs of elements \(\{1,\dots,n\}\) and whose edges are drawn between disjoint pairs. In the present paper, we establish that the triangle saturation number of the Kneser graph is equal to \((3/2)n^2+O(n)\) and also find its exact values for small \(n\) .