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

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

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


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




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

Математические заметки, 2021, том 109, выпуск 1, страницы 36–46
DOI: https://doi.org/10.4213/mzm12784 (Mi mzm12784) 		 
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Решение задачи об описательной сложности изоморфизма подграфа с помощью кнезеровских графов

В. А. Вороновa, Е. А. Дергачевb, М. Е. Жуковскийc, А. М. Неопрятнаяb

a Кавказский математический центр, Адыгейский государственный университет, г. Майкоп
b Адыгейский государственный университет, г. Майкоп
c Московский физико-технический институт (национальный исследовательский университет), Московская облаcть, г. Долгопрудный
PDF полного текста (482 kB) Список цитирования (2)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.4213/mzm12784
Аннотация: В работе изучается задача нахождения наименьшего числа переменных формулы первого порядка, записывающей свойство input-графа содержать подграф, изоморфный заданному pattern-графу. Рассматриваются input-графы, имеющие достаточно большую связность. Ранее эта задача была решена для всех pattern-графов с 4 вершинами, кроме двух – простого цикла и diamond-графа. В настоящей работе мы нашли значение этой величины для двух оставшихся графов.
Библиография: 8 названий.
Ключевые слова: кнезеровские графы, input-графы, pattern-графы, игра Эренфойхта.
Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации НШ-2540.2020.1
Российский научный фонд 18-71-00069
Исследование М. Е. Жуковского выполнено за счет гранта Российского научного фонда (грант № 18-71-00069). Исследование В. А. Воронова выполнено за счет программы “Ведущие научные школы” (грант № НШ-2540.2020.1). Утверждение 1 доказано В. А. Вороновым. Утверждение 2 и вторая часть теоремы 2 доказаны М. Е. Жуковским. Введение, п. 2, обзор известных результатов о кнезеровском графе и первая часть теоремы 1 выполнены А. М. Неопрятной и Е. А. Дергачевым.
Поступило: 06.05.2020
Исправленный вариант: 23.06.2020
Англоязычная версия:
Mathematical Notes, 2021, Volume 109, Issue 1, Pages 29–37
DOI: https://doi.org/10.1134/S0001434621010041
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.17
Образец цитирования: В. А. Воронов, Е. А. Дергачев, М. Е. Жуковский, А. М. Неопрятная, “Решение задачи об описательной сложности изоморфизма подграфа с помощью кнезеровских графов”, Матем. заметки, 109:1 (2021), 36–46; Math. Notes, 109:1 (2021), 29–37
Цитирование в формате AMSBIB
\RBibitem{VorDerZhu21}
\by В.~А.~Воронов, Е.~А.~Дергачев, М.~Е.~Жуковский, А.~М.~Неопрятная
\paper Решение задачи об описательной сложности изоморфизма подграфа
с~помощью кнезеровских графов
\jour Матем. заметки
\yr 2021
\vol 109
\issue 1
\pages 36--46
\mathnet{http://mi.mathnet.ru/mzm12784}
\crossref{https://doi.org/10.4213/mzm12784}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4223893}
\elib{https://elibrary.ru/item.asp?id=46905021}
\transl
\jour Math. Notes
\yr 2021
\vol 109
\issue 1
\pages 29--37
\crossref{https://doi.org/10.1134/S0001434621010041}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000670512900004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85109140998}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mzm12784
  • https://doi.org/10.4213/mzm12784
  • https://www.mathnet.ru/rus/mzm/v109/i1/p36
    • Эта публикация цитируется в следующих 2 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Математические заметки Mathematical Notes
    Статистика просмотров:
    Страница аннотации:292
    PDF полного текста:51
    Список литературы:40
    Первая страница:17
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024