?
Некоторые результаты о наследственных классах графов
Вестник Нижегородского университета им. Н.И. Лобачевского. 2011. Т. 6. № 1. С. 169–173.
Рассматриваются вопросы структурного описания и асимптотического перечисления наследственных классов графов, исследуется сложность некоторых задач на таких классах.
Пятов П. Н., Пивоваров П. А., / Series math "arxiv.org". 2026. No. 2609.06274.
Добавлено: 24 сентября 2026 г.
Медведев В. О., / Series arXiv "math". 2026.
We study complete static manifolds with boundary admitting a nowhere-vanishing static potential. Our main result shows that, under a natural lower bound relating the scalar curvature and the boundary mean curvature, a simple static manifold with boundary must in fact have positive scalar curvature, negative boundary mean curvature, and be compact; we also obtain explicit ...
Добавлено: 19 сентября 2026 г.
Поддьяков А. Н., / Series Social Science Research Network "Social Science Research Network". 2026. No. 7437658.
Добавлено: 15 сентября 2026 г.
Починка О. В., Шмуклер В. И., / Series math.RT "arXiv:1808.06395 [math.RT]". 2026.
Добавлено: 31 августа 2026 г.
Болбачан В. С., / Series math "arxiv.org". 2024.
Полилогарифмы Чжоу — это специальные функции, возникающие при явном описании отображения регулятора Бейлинсона. Наиболее интересное функциональное уравнение для этой функции отражает тот факт, что она обращается в нуль на границе в комплексе циклов Блоха. Мы показываем, что это функциональное уравнение формально вытекает из более простых свойств: кососимметричности, функториальности и мультипликативности. Для доказательства этого мы рассматриваем ...
Добавлено: 16 июля 2026 г.
Болбачан В. С., / Series math "arxiv.org". 2024.
Пусть K поле характеристики ноль. Мы доказываем что его когомологии в степени m-1 и весе m рационально изоморфны когомологиям полилогарифмического комплекса в соответствующей степени. Это дает частичное расширение теоремы Суслина, описывающую неразложимую K теорию K_3 для поля. ...
Добавлено: 16 июля 2026 г.
Панов В. А., Рябченко А. П., / Series arXiv "stat.ME". 2026. No. 2607.05048.
Добавлено: 9 июля 2026 г.
Добавлено: 11 июня 2026 г.
Талецкий Д. С., Дискретный анализ и исследование операций 2024 Т. 31 № 1 С. 109–128
Множество J_k вершин графа называется k-доминирующим независимым (k > 1), если его вершины попарно не смежны и каждая вершина не из J_k смежна хотя бы с k вершинами из J_k. В этой статье получены новые оценки количества k-доминирующих независимых множеств при различных значениях k > 2 в некоторых классах планарных графов. ...
Добавлено: 25 марта 2024 г.
Талецкий Д. С., Математический сборник 2023 Т. 214 № 11 С. 133–156
Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа k ⩾ 1, то количество его k-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является k-регулярным. Эта гипотеза доказана для случая k ∈ {1,2}. ...
Добавлено: 2 ноября 2023 г.
Талецкий Д. С., Дискретный анализ и исследование операций 2023 Т. 30 № 3 С. 111–131
Множество вершин графа называется k-дистанционным независимым, если расстояние между любыми двумя его вершинами больше некоторого целого числа k ⩾ 1. В работе рассматривается задача описания n-вершинных деревьев фиксированного диаметра d, содержащих максимально и минимально возможное число k-дистанционных независимых множеств среди всех таких деревьев. Задача на максимум решается для случая 1 < k < d ⩽ ...
Добавлено: 13 июня 2023 г.
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в ...
Добавлено: 6 декабря 2022 г.
Талецкий Д. С., Математические заметки 2021 Т. 109 № 2 С. 276–289
Рассматривается задача описания 𝑛-вершинных деревьев диаметра 𝑑, содержащих минимально возможное количество независимых множеств. Эта задача решается для случаев 𝑑 = 6, 𝑛 > 160 и 𝑑 = 7, 𝑛 > 400. ...
Добавлено: 24 ноября 2020 г.
Талецкий Д. С., Малышев Д. С., Дискретная математика 2020 Т. 32 № 2 С. 71–84
В работе полностью описаны деревья с максимально возможным количеством наибольших независимых множеств среди всех n-вершинных деревьев, содержащих ровно l листьев. При любых значениях параметров n и l экстремальное дерево единственно. Оно является результатом отождествления концов l простых путей. ...
Добавлено: 30 июня 2020 г.
Малышев Д. С., Журнал Средневолжского математического общества 2020 Т. 22 № 1 С. 38–47
Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, возможно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Наследственный класс графов — множество обыкновенных графов, замкнутое относительно изоморфизма и удаления вершин. Любой такой класс может быть задан множеством своих запрещенных порожденных подграфов. Известен сложностной статус задачи о вершинной 3-раскраске ...
Добавлено: 26 марта 2020 г.
Талецкий Д. С., Журнал Средневолжского математического общества 2017 Т. 19 № 2 С. 105–116
В настоящей работе рассматриваются количественные характеристики максимальных независимых множеств в графах-решетках. В ней используются методы комбинаторного анализа, перечислительной комбинаторики, математического анализа и линейной алгебры. Получен явный вид производящих функций количества максимальных независимых множеств в цилиндрических и тороидальных решетках ширины 4,5,64,5,6. Доказано, что пределы корней mnmn-ой степени из количества (максимальных) независимых множеств в прямоугольных, цилиндрических и тороидальных m×nm×n-решетках существуют ...
Добавлено: 29 октября 2019 г.
Сироткин Д. В., Малышев Д. С., Дискретная математика 2017 Т. 29 № 3 С. 114–125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Добавлено: 7 сентября 2017 г.