RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 2024 Volume 116, Issue 2, Pages 185–194 (Mi mzm14170)

Saturation in Kneser graphs

S. V. Vakhrusheva, M. E. Zhukovskiib, A. Yu. Skorkinc

a Saint Petersburg State University
b The University of Sheffield
c Adyghe State University, Maikop

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$.

Keywords: Kneser graph, saturation number, triangle.

UDC: 519.176

Received: 09.10.2023
Revised: 22.01.2024

DOI: 10.4213/mzm14170


 English version:
Mathematical Notes, 2024, 116:2, 200–208


© Steklov Math. Inst. of RAS, 2024