Математический сборник
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Матем. сб.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Математический сборник, 2023, том 214, номер 11, страницы 133–156
DOI: https://doi.org/10.4213/sm9870 (Mi sm9870) 		 
О количестве независимых и $k$-доминирующих множеств в графах со средней степенью вершин не более $k$

Д. С. Талецкий

Лаборатория алгоритмов и технологий анализа сетевых структур, Национальный исследовательский университет "Высшая школа экономики", г. Нижний Новгород
PDF полного текста (660 kB) Первая страница PDF английской версии (541 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/sm9870
Аннотация: Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа $k \geqslant 1$, то количество его $k$-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является $k$-регулярным. Эта гипотеза доказана для случая $k \in \{1,2\}$.
Библиография: 10 названий.
Ключевые слова: независимое множество, доминирующее множество, $k$-доминирующее множество, перечислительная комбинаторика.
Финансовая поддержка Номер гранта
Программа фундаментальных исследований НИУ ВШЭ
Статья подготовлена в ходе проведения исследования в рамках Программы фундаментальных исследований Национального исследовательского университета “Высшая школа экономики” (НИУ ВШЭ).
Поступила в редакцию: 22.12.2022 и 20.06.2023
Англоязычная версия:
Sbornik: Mathematics, 2023, Volume 214, Issue 11, Pages 1627–1650
DOI: https://doi.org/10.4213/sm9870e
Реферативные базы данных:
Тип публикации: Статья
MSC: 05C30
Образец цитирования: Д. С. Талецкий, “О количестве независимых и $k$-доминирующих множеств в графах со средней степенью вершин не более $k$”, Матем. сб., 214:11 (2023), 133–156; D. S. Taletskii, “On the number of independent and $k$-dominating sets in graphs with average vertex degree at most $k$”, Sb. Math., 214:11 (2023), 1627–1650
Цитирование в формате AMSBIB
\RBibitem{Tal23}
\by Д.~С.~Талецкий
\paper О количестве независимых и $k$-доминирующих множеств в графах со средней степенью вершин не более $k$
\jour Матем. сб.
\yr 2023
\vol 214
\issue 11
\pages 133--156
\mathnet{http://mi.mathnet.ru/sm9870}
\crossref{https://doi.org/10.4213/sm9870}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4720897}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2023SbMat.214.1627T}
\transl
\by D.~S.~Taletskii
\paper On the number of independent and $k$-dominating sets in graphs with average vertex degree at most~$k$
\jour Sb. Math.
\yr 2023
\vol 214
\issue 11
\pages 1627--1650
\crossref{https://doi.org/10.4213/sm9870e}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001191951300005}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85188521586}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/sm9870
  • https://doi.org/10.4213/sm9870
  • https://www.mathnet.ru/rus/sm/v214/i11/p133
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Математический сборник Sbornik: Mathematics
    Статистика просмотров:
    Страница аннотации:293
    PDF русской версии:5
    PDF английской версии:24
    HTML русской версии:43
    HTML английской версии:100
    Список литературы:20
    Первая страница:8
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024