Числа независимости случайных подграфов графов Джонсона
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 1 (65) т.17, 2025 года.
Бесплатный доступ
В работе рассматриваются обобщенные графы Джонсона G(n, r, s) и их случайные подграфы Gp(n, r, s). Основной темой исследования являются асимптотические оценки числа независимости (максимального независимого множества) в таких случайных подграфах. Сформулирована и доказана теорема об асимптотической оценке снизу числа независимости случайного графа Джонсона.
Похожие статьи в разделе Метафизика
Короткий адрес: https://sciup.org/142245197
IDS: 142245197 | УДК: 111.111
Independence numbers of random subgraphs of Johnson graphs
In this paper, we consider generalized Johnson graphs G(n, r, s) and their random subgraphs Gp(n, r, s). The main topic of the study is asymptotic estimates of the independence number (maximal independent set) in such random subgraphs. A theorem on asymptotic estimation from below of the independence number of a Johnson random graph is formulated and proved.
