This article is cited in 2 papers

Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph

N. A. Dubinin^a, E. A. Neustroeva^a, A. M. Raigorodskii^abcd, Ya. K. Shubin<sup>a

a</sup> Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Region, Russia
^b Lomonosov Moscow State University, Moscow, Russia
^c Adyghe State University, Maikop, Russia
^d Buryat State University named after D. Banzarov, Ulan-Ude, Russia

Abstract: Lower and upper bounds are derived for the minimum number of edges in subgraphs of the graph $G(n,3,1)$ induced by $l$ vertices, where $l \sim cn^2$. The results in this work improve the estimates for this quantity that were obtained previously in the case under study.
Bibliography: 16 titles.

Keywords: distance graphs, Johnson graphs, extremal graph theory.

MSC: 05C35, 05C69

Received: 31.10.2023 and 05.12.2023

DOI: 10.4213/sm10021

 English version: Sbornik: Mathematics, 2024, 215:5, 634–657

Bibliographic databases:

• 
• 
• 
• 
•