|
Эта публикация цитируется в 28 научных статьях (всего в 28 статьях)
Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов
Л. И. Боголюбскийa, А. С. Гусевa, М. М. Пядёркинa, А. М. Райгородскийabc a Механико-математический факультет,
Московский государственный университет имени М.В.Ломоносова
b Факультет инноваций и высоких технологий,
Московский физико-технический институт (государственный университет)
c Институт математики и информатики, Бурятский государственный университет, г. Улан-Удэ
Аннотация:
Работа связана с классической задачей Нелсона–Хадвигера о поиске хроматического числа
дистанционных графов в $\mathbb R^n$. В основном мы рассматриваем класс графов $G(n, r,s)=(V(n, r), E(n,r,s))$, определeнных так:
\begin{gather*}
V(n, r)=\bigl\{\mathbf{x}=(x_1,\dots,x_n) : x_i\in\{0, 1\},\, x_1+\dots+x_n=r\bigr\},
\\
E(n,r,s)=\bigl\{\{\mathbf{x}, \mathbf{y}: (\mathbf{x}, \mathbf{y})=s\}\bigr\},
\end{gather*}
где $(\mathbf{x}, \mathbf{y})$ – евклидово скалярное произведение. В частности, хроматическое число $G(n,3,1)$ недавно было найдено Й. Балогом, А. В. Косточкой, А. М. Райгородским. Мы изучаем случайные подграфы $\mathscr{G}(G(n,r,s), p)$, ребра в которых выбираются независимо из множества $E(n,r,s)$ каждое с вероятностью $p$. Найдены нетривиальные нижние и верхние оценки числа независимости и хроматического числа таких графов. В случае, когда $r-s$ есть степень простого числа и $r\leq 2s+1$, удалось установить порядок $\alpha(\mathscr{G}(G(n,r,s), p))$ и $\chi(\mathscr{G}(G(n,r,s), p))$.
Библиография: 51 название.
Ключевые слова:
случайный граф, дистанционный граф, число независимости, хроматическое число.
Поступила в редакцию: 10.02.2014 и 12.12.2014
Образец цитирования:
Л. И. Боголюбский, А. С. Гусев, М. М. Пядёркин, А. М. Райгородский, “Числа независимости и хроматические числа случайных подграфов некоторых дистанционных графов”, Матем. сб., 206:10 (2015), 3–36; L. I. Bogolubsky, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Independence numbers and chromatic numbers of the random subgraphs of some distance graphs”, Sb. Math., 206:10 (2015), 1340–1374
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm8344https://doi.org/10.4213/sm8344 https://www.mathnet.ru/rus/sm/v206/i10/p3
|
Статистика просмотров: |
Страница аннотации: | 939 | PDF русской версии: | 432 | PDF английской версии: | 49 | Список литературы: | 60 | Первая страница: | 43 |
|