RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2017, том 53, выпуск 4, страницы 3–15 (Mi ppi2249)

Эта публикация цитируется в 9 статьях

Теория кодирования

Числа независимости случайных подграфов некоторого дистанционного графа

Н. М. Деревянко, С. Г. Киселев

Московский физико-технический институт (государственный университет)

Аннотация: Дистанционным графом $G(n,2,1)$ называется граф, вершины которого отождествляются с двухэлементными подмножествами множества $\{1,2,\dots,n\}$, а ребро между вершинами проведено в том случае, если соответствующие подмножества имеют ровно один общий элемент. Случайный подграф $G_p(n,2,1)$ в модели Эрдеша–Реньи получается включением каждого ребра графа $G(n,2,1)$ с вероятностью $p$ независимо от остальных ребер. Найдена нижняя оценка числа независимости случайного подграфа $G_{1/2}(n,2,1)$.

УДК: 621.391.1+519.1

Поступила в редакцию: 25.02.2017
После переработки: 04.05.2017


 Англоязычная версия: Problems of Information Transmission, 2017, 53:4, 307–318

Реферативные базы данных:


© МИАН, 2024