Geodesic
Saturation in Kneser graphs
Matematičeskie zametki, Tome 116 (2024) no. 2, pp. 185-194.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{MZM_2024_116_2_a1,
     author = {S. V. Vakhrushev and M. E. Zhukovskii and A. Yu. Skorkin},
     title = {Saturation in {Kneser} graphs},
     journal = {Matemati\v{c}eskie zametki},
     pages = {185--194},
     publisher = {mathdoc},
     volume = {116},
     number = {2},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a1/}
}
TY  - JOUR
AU  - S. V. Vakhrushev
AU  - M. E. Zhukovskii
AU  - A. Yu. Skorkin
TI  - Saturation in Kneser graphs
JO  - Matematičeskie zametki
PY  - 2024
SP  - 185
EP  - 194
VL  - 116
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a1/
LA  - ru
ID  - MZM_2024_116_2_a1
ER  - 
%0 Journal Article
%A S. V. Vakhrushev
%A M. E. Zhukovskii
%A A. Yu. Skorkin
%T Saturation in Kneser graphs
%J Matematičeskie zametki
%D 2024
%P 185-194
%V 116
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a1/
%G ru
%F MZM_2024_116_2_a1
S. V. Vakhrushev; M. E. Zhukovskii; A. Yu. Skorkin. Saturation in Kneser graphs. Matematičeskie zametki, Tome 116 (2024) no. 2, pp. 185-194. http://geodesic.mathdoc.fr/item/MZM_2024_116_2_a1/

[1] P. Erdos, A. Hajnal, J. W. Moon, “A problem in graph theory”, Amer. Math. Monthly, 71 (1964), 1107–1110 | DOI | MR

[2] D. D. Cherkashin, A. B. Kulikov, A. M. Raigorodskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, Discrete Appl. Math., 243 (2018), 125–131 | DOI | MR

[3] A. M. Raigorodskii, “On the chromatic numbers of spheres in $\mathbb{R}^n$”, Combinatorica, 32:1 (2012), 111–123 | DOI | MR

[4] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR

[5] Z. Nagy, “A certain constructive estimate of the Ramsey number”, Mat. Lapok., 23 (1972), 301–302 | MR

[6] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Math. Library, 16, North-Holland, Amsterdam–New York, 1977 | MR

[7] Y. Chen, “Triangle-free Hamiltonian Kneser graphs”, J. Combin. Theory Ser. B, 89:1 (2003), 1–16 | DOI | MR

[8] L. Lovasz, “Kneser's conjecture, chromatic number, and homotopy”, J. Combin. Theory Ser. A, 25:3 (1978), 319–324 | DOI | MR

[9] M. Valencia-Pabon, J. Vera, “On the diameter of Kneser graphs”, Discrete Math., 305:1–3 (2005), 383–385 | DOI | MR

[10] A. M. Raigorodskii, “On the stability of the independence number of a random subgraph”, Dokl. Math., 96:3 (2017), 628–630 | DOI | MR