Аннотация:
В данной работе нами получена нижняя оценка количества ребер в дистанционном графе Γ в слойке R2×[0,ε]d, которая связывает между собой количество ребер e(Γ), число вершин ν(Γ) и число независимости α(Γ), а именно доказано, что e(Γ)⩾19νΓ)−50α(Γ)3. Этот результат является обобщением предыдущей аналогичной оценки для дистанционных графов на плоскости и существенным улучшением Турановской оценки в случае, когда 15⩽α(Γ)ν(Γ)⩽27. Библ. – 18 назв.
Ключевые слова:
дистанционный граф, число независимости, Турановские оценки.
Образец цитирования:
Л. Э. Шабанов, “Турановские оценки для дистанционных графов в тонкой слойке”, Комбинаторика и теория графов. IX, Зап. научн. сем. ПОМИ, 464, ПОМИ, СПб., 2017, 132–168; J. Math. Sci. (N. Y.), 236:5 (2019), 554–578
\RBibitem{Sha17}
\by Л.~Э.~Шабанов
\paper Турановские оценки для дистанционных графов в~тонкой слойке
\inbook Комбинаторика и теория графов.~IX
\serial Зап. научн. сем. ПОМИ
\yr 2017
\vol 464
\pages 132--168
\publ ПОМИ
\publaddr СПб.
\mathnet{http://mi.mathnet.ru/znsl6526}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2019
\vol 236
\issue 5
\pages 554--578
\crossref{https://doi.org/10.1007/s10958-018-4133-1}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl6526
https://www.mathnet.ru/rus/znsl/v464/p132
Эта публикация цитируется в следующих 6 статьяx:
Я. К. Шубин, “О минимальном числе ребер в индуцированных подграфах специальных
дистанционных графов”, Матем. заметки, 111:6 (2022), 929–939; Ya. K. Shubin, “On the Minimal Number of Edges in Induced Subgraphs of Special Distance Graphs”, Math. Notes, 111:6 (2022), 961–969
Ф. А. Пушняков, А. М. Райгородский, “Оценка числа ребер в особых подграфах
некоторого дистанционного графа”, Матем. заметки, 107:2 (2020), 286–298; Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332
A. A. Sagdeev, “On the Chromatic Numbers Corresponding to Exponentially Ramsey Sets”, J Math Sci, 247:3 (2020), 488
Ф. А. Пушняков, “О количествах ребер в порожденных подграфах
некоторых дистанционных графов”, Матем. заметки, 105:4 (2019), 592–602; Ph. A. Pushnyakov, “The Number of Edges in Induced Subgraphs of Some Distance Graphs”, Math. Notes, 105:4 (2019), 582–591
К. Д. Коваленко, А. М. Райгородский, “Системы представителей”, Матем. заметки, 106:3 (2019), 387–394; K. D. Kovalenko, A. M. Raigorodskii, “Systems of Representatives”, Math. Notes, 106:3 (2019), 372–377
A. M. Raigorodskii, E. D. Shishunov, “On the Independence Numbers of Distance Graphs with Vertices in {–1, 0, 1}n”, Dokl. Math., 100:2 (2019), 476