• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • О числе вечного доминирования планарных графов диаметра 2
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
June 22, 2026
‘In Science, You Are Your Own Boss
Polina Nasledskova is interested in identifying gaps in linguistics and topics that have been overlooked by other researchers. In an interview for the  Young Scientists of HSE University project, she spoke about rare ordinal numerals in Nakh-Daghestanian languages, the benefits of knitting for concentration, and the beauty of the Patriarshy Bridge.
June 19, 2026
HSE Researchers Determine Which Internet Users Are More Likely to Fact-Check
Researchers at HSE University examined the strategies employed by Russian internet users to verify unreliable information and the factors that motivate them to do so. The study found that more than half of users who encounter potentially false information online attempt to verify it by locating the original source. The likelihood of fact-checking is influenced by several factors, including age, place of residence, social status, information literacy skills, and the use of AI. The findings have been published in Monitoring of Public Opinion: Economic and Social Changes.
June 5, 2026
'Im Used to Producing Distilled Knowledge'
Ivan Rubachev works in a HSE University laboratory established jointly with Yandex Research, where he focuses on machine learning with tabular data. In this interview with the HSE Young Scientists project, he discusses why following a vibe can be better than goal-setting, explains the concept of the Neural Turing Machine, and argues why withholding scientific knowledge is counterproductive.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

О числе вечного доминирования планарных графов диаметра 2

Дискретный анализ и исследование операций. 2025. Т. 32. № 1. С. 122–144.
Taletskii D.
Research target: Mathematics
Language: Russian
Full text
Keywords: планарный графдоминирующее множествовечное доминирующее множествочисло вечного доминирования
Publication based on the results of:
Network and graph models, algorithmic complexity and data mining (2025)
Similar publications
Open Hurwitz numbers and the mKP hierarchy
Buryak A., Tessler R., Troshkin M., Journal of Geometry and Physics 2026 Vol. 223 Article 105783
We give a natural definition of open Hurwitz numbers, where the weight of each ramified covering includes an integer parameter N taken to the power that is equal to the number of boundary components of a Riemann surface with boundary mapping to . We prove that the resulting sequence of partition functions, depending on , is a tau-sequence of ...
Added: June 19, 2026
Bihamiltonian structure of the DR hierarchy in the semisimple case
Buryak A., Rossi P., Communications in Mathematical Physics 2025 Vol. 406 Article 205
Of the two approaches to integrable systems associated to semisimple cohomological field theories (CohFTs), the one suggested by Dubrovin and Zhang and the more recent one using the geometry of the double ramification (DR) cycle, the second has the advantage of being very explicit. The Poisson operator of the DR hierarchy is , where  is the metric ...
Added: June 19, 2026
Advances in Information Retrieval: 48th European Conference on Information Retrieval, ECIR 2026, Delft, The Netherlands, March 29 – April 2, 2026, Proceedings, Part II. (LNCS, volume 16484)
Cham: Springer Publishing Company, 2026.
The four-volume set LNCS 16483-16486 constitutes the refereed conference proceedings of the 48th European Conference on Information Retrieval, ECIR 2026, held in Delft, The Netherlands, during March 29–April 2, 2026. The 46 full papers and 37 short papers presented together with 10 findings papers, 9 reproducibility papers, 17 resource papers, 11 workshop papers, 7 tutorial papers, ...
Added: June 18, 2026
Искусственный интеллект как роза научной деятельности: исследование Тимоти Гауэрса
Poddiakov A., Троицкий вариант. Наука 2026 № 12 С. 24–25
В научно-популярной заметке представлен обзор содержания поста филдсовского медалиста Тимоти Гауэрса о возможностях ИИ в математике и содержания комментариев под постом. Обзор сделан в основном чат-ботом DeepSeek. В заключение обсуждается возможность не только решения задач искусственным интеллектом, но и их постановки. ...
Added: June 18, 2026
Optimal Extraction with an Impact on Diffusion-Jump Pricing
Garzón J., Mora Rodríguez J., Moreno-Franco H. A., Applied Mathematics and Optimization 2026 Vol. 94 No. 10 P. 1–43
We study an optimal extraction problem where the agent’s actions in the spot market exert an additive proportional negative impact on the commodity price. The commodity price dynamics, prior to any activity by the agent, evolve according to a drifted Brownian motion with jumps. The agent’s primary aim is to identify an optimal extraction strategy ...
Added: June 17, 2026
Об устройстве целевого приёма в России.
Nesterov A. S., Журнал Новой экономической ассоциации 2026
В этой статье рассматривается целевой приём в вузы в России с точки зрения науки об устройстве рынков сочетания и экономических механизмов (matching market and mechanism design), ключевого направления современной теории игр. Мы изучаем механизм целевого приёма -- набор правил, по которым устраивается трёхстороннее сочетание между абитуриентом, заказчиком и образовательной программой. Используемый в России механизм имеет ...
Added: June 16, 2026
On the Ramsey Number R(K_{1,s},P_t)
Kh. Kh. Abdullin, D. B. Mokeev, D. S. Taletskii, Mathematical notes 2026 Vol. 119 No. 1 P. 3–7
By the Ramsey number R(K1,s,Pt) one means the least positive integer n such that, for every n-vertex graph G, the following condition holds: either G contains a vertex of degree at least s or the complement of G contains a simple t-path. In this paper, we fi nd precise values of R(K1,s,Pt) for certain values ...
Added: June 10, 2026
Innovations in Information and Decision Sciences. Proceedings of the 13th International Conference on Frontiers in Intelligent Computing: Theory and Applications (FICTA 2025), Volume 4
Springer, 2026.
The book presents the proceedings of the 13th International Conference on Frontiers of Intelligent Computing: Theory and Applications (FICTA 2024), held at Intelligent Systems Research Group (ISRG), London Metropolitan University, London, United Kingdom, during June 6–7, 2025. Researchers, scientists, engineers and practitioners exchange new ideas and experiences in the domain of intelligent computing theories with ...
Added: June 8, 2026
Wave dynamics within the Whitham-Ostrovsky equation
Flamarion M. V., Pelinovsky E., Nonlinear Dynamics 2026 Vol. 114 Article 784
In this article, we investigate wave packet and solitary wave dynamics in the Whitham–Ostrovsky (WO) equation. By means of a multiple-scales expansion, we formally derive a nonlinear Schrödinger (NLS) equation governing the envelope evolution.The corresponding modulational stability diagram is then obtained using the Lighthill criterion. We show that sufficiently large values of the low-frequency dispersive term render ...
Added: June 5, 2026
On structural stability of 3-diffeomorphisms with the Smale solenoid attractor–repeller dynamics
Medvedev T. V., Pochinka O., Chaos 2026 Vol. 36 No. 6 Article 063107
We consider 3-diffeomorphisms with source–sink dynamics where Smale solenoids play the role of the source and the sink (NSSS-diffeomorphisms). It is known that such diffeomorphisms exist only on lens spaces. On the 3-sphere, every NSSS-diffeomorphism is associated with an exchangeable braid. An exchangeable braid with the strand number n was constructed for each n   3 in such a way ...
Added: June 4, 2026
Некоторые полные сложностные дихотомии для задачи о доминирующем множестве
Дахно Г. С., Malyshev D., Математические заметки 2025 Т. 117 № 1 С. 62–78
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданного размера, что каждая вершина вне подмножества имеет хотя бы одного соседа в данном подмножестве. ...
Added: December 3, 2024
О количестве k-доминирующих независимых множеств в планарных графах
Taletskii D., Дискретный анализ и исследование операций 2024 Т. 31 № 1 С. 109–128
The set of graph vertices J_k is called k-dominating independent (k > 1) if its vertices are pairwise adjacent and every vertex not from J_k is adjacent to at least k vertices from J_k. In the presentb paper we obtain new upper bounds for the number of k-dominating independent sets for k > 2 in ...
Added: March 25, 2024
О количестве независимых и k-доминирующих множеств в графах со средней степенью вершин не более k
Taletskii D., Математический сборник 2023 Т. 214 № 11 С. 133–156
Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа k ⩾ 1, то количество его k-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является k-регулярным. Эта гипотеза доказана для случая k ∈ {1,2}. ...
Added: November 2, 2023
On a Countable Family of Boundary Graph Classes for the Dominating Set Problem
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
A hereditary class is a set of simple graphs closed under deletion of vertices; every such class is defined by the set of its minimal forbidden induced subgraphs. If this set is finite, then the class is said to be finitely defined. The concept of a boundary class is a useful tool for the analysis ...
Added: December 6, 2022
On 3-colouring of graphs with short faces and bounded maximum vertex degree
Sirotkin D., Malyshev D., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760–766
The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree ...
Added: June 5, 2021
О сложности построения 3-раскраски с короткими гранями
Sirotkin D., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199–205
The vertex 3-colourability problem is to determine for a given graph whether one can divide its vertex set into three subsets of pairwise non-adjacent vertices. This problem is NP-complete in the class of planar graphs, but it becomes polynomial-time solvable for planar triangulations, i.e. planar graphs, all facets of which (including external) are triangles. Additionally, ...
Added: July 2, 2018
Способ редукции графов и его приложения
Sirotkin D., Malyshev D., Дискретная математика 2017 Т. 29 № 3 С. 114–125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Added: September 7, 2017
Граничные классы для задачи о независимом множестве в классе планарных графов
Malyshev D., Вестник Нижегородского университета им. Н.И. Лобачевского 2007 № 2 С. 165–168
The Independent Set Problem for planar graphs is known to be NP-complete. In this paper, its polynomial solvability for some subclasses of planar graphs is proved. ...
Added: November 25, 2012
The Maximum Independent Set Problem in Planar Graphs
Alekseev V., Lozin V. V., Malyshev D. et al., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96–107
We study the computational complexity of finding a maximum independent set of vertices in a planar graph. In general, this problem is known to be NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify a graph parameter to which the complexity of the problem is sensible and produce a number of both negative ...
Added: November 7, 2012
Классы планарных графов с полиномиально разрешимой задачей о независимом множестве
Malyshev D., Alekseev V., Дискретный анализ и исследование операций 2008 Т. 15 № 1 С. 3–10
Доказывается полиномиальная разрешимость задачи о независимом множестве для бесконечного семейства подмножеств класса планарных графов. ...
Added: August 31, 2012
Planar graph classes with the independent set problem solvable in polynomial time
Malyshev D., Alekseev V., Journal of Applied and Industrial Mathematics 2008 Vol. 3 No. 1 P. 1–5
The polynomial solvability of the independent set problem is proved for an infinite family of subsets of the class of planar graphs. ...
Added: August 31, 2012
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit