• 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 25, 2026
HSE Researchers Make Aldehydes Perform Dual Function
Chemists from HSE University have discovered a way to carry out a reductive addition reaction without using an external reducing agent. Instead, the required 'resource' is supplied by the aldehyde itself, one of the reaction participants. This approach helps prevent unwanted side reactions, reduces toxicity, and simplifies the production and synthesis of organic molecules, including those used in the manufacture of medicines. The study has been published in Journal of Catalysis.
June 25, 2026
HSE Scientists Explain Why Findings in Autism Research Differ
Researchers from the Cognitive Health and Intelligence Centre at HSE University conducted the first-ever systematic review of studies on the specifics of emotion-from-motion perception in autism. The review showed that differences found between autistic and non-autistic individuals are largely associated with the experimental design and the types of tasks given to study participants. The review findings have been published in Research in Autism.
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.

 

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
Нахождение формальных степенно–логарифмических разложений решений 𝑞–разностных уравнений
Gaianov N., Parusnikova A., Уфимский математический журнал 2026 Т. 18 № 2 С. 14–22
We consider an algebraic 𝑞–difference equation. We propose a sufficient condition for the existence of a formal power–logarithmic expansion in the vicinity of zero of the solution to such an equation. We apply this sufficient condition to construct the formal expansion of a solution to a certain 𝑞–difference analogue of the fifth Painlevé equation for particular ...
Added: June 24, 2026
Open r-spin theory II: The analogue of Witten's conjecture for r-spin disks
Buryak A., Clader E., Tessler R., Journal of Differential Geometry 2024 Vol. 128 No. 1 P. 1–75
We conclude the construction of $r$-spin theory in genus zero for Riemann surfaces with boundary. In particular, we define open $r$-spin intersection numbers, and we prove that their generating function is closely related to the wave function of the $r$th Gelfand--Dickey integrable hierarchy. This provides an analogue of Witten's $r$-spin conjecture in the open setting ...
Added: June 23, 2026
Tautological relations and integrable systems
Buryak A., Shadrin S., Epijournal de Geometrie Algebrique 2024 Vol. 8
We present a family of conjectural relations in the tautological cohomology of the moduli spaces of stable algebraic curves of genus g with n marked points. A large part of these relations has a surprisingly simple form: the tautological classes involved in the relations are given by stable graphs that are trees and that are decorated only by powers ...
Added: June 23, 2026
Counting meromorphic differentials on $CP^1$
Buryak A., Rossi P., Letters in Mathematical Physics 2024 Vol. 114 Article 97
We give explicit formulas for the number of meromorphic differentials on $CP^1$ with two zeros and any number of residueless poles and for the number of meromorphic differentials on $CP^1$ with one zero, two poles with unconstrained residue and any number of residueless poles, in terms of the orders of their zeros and poles. These ...
Added: June 23, 2026
Moduli spaces of residueless meromorphic differentials and the KP hierarchy
Buryak A., Rossi P., Zvonkine D., Geometry and Topology 2024 Vol. 28 P. 2793–2824
We prove that the cohomology classes of the moduli spaces of residueless meromorphic differentials, ie the closures, in the moduli space of stable curves, of the loci of smooth curves whose marked points are the zeros and poles of prescribed orders of a meromorphic differential with vanishing residues, form a partial cohomological field theory (CohFT) of ...
Added: June 23, 2026
DR-иерархии: от пространств модулей кривых к интегрируемым системам
Buryak A., Труды Математического института им. В.А. Стеклова РАН 2024 Т. 325 С. 26–66
The main goal of the paper is to show that the DR hierarchies, introduced by the author in an earlier paper, allow one to establish, in the most clear way, a relation between the topology of the Deligne–Mumford compactification of the moduli space of smooth algebraic curves of genus g with n marked points and integrable systems ...
Added: June 23, 2026
Growth in noncommutative algebras and entropy in derived categories
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Multilinear nilalgebras and the Jacobian theorem
Piontkovski D., / Series arXiv "math". 2025.
If a symmetric multilinear algebra is weakly nil, then it is Engel. This result may be regarded as an infinite-dimensional analogue of the well-known Jacobian theorem, which states that if a polynomial mapping has a polynomial inverse, then its Jacobian matrix is invertible. This refines a theorem of Gerstenhaber and partially answers a question posed ...
Added: June 23, 2026
Международная конференция «Математические идеи академика П.Л. Чебышёва, их приложения в естественных науках и технологи- ях искусственного интеллекта», приуроченная к 205-й годовщине со дня его рождения» : Материалы конференции. / (Обнинск, 14–16 мая 2026 г.): Материалы конференции. Под ред. акад. В.Б. Бетелина. — Калуга: Калужский печатный двор, 2026. — 232 с.
Калужский печатный двор, 2026.
Conference Proceedings INTERNATIONAL CONFERENCE “Mathematical Ideas of Academician P.L. Chebyshev, Their Applications in Natural Sciences and Artificial Intelligence Technologies” dedicated to the 205th anniversary of his birth ...
Added: June 20, 2026
Численное решение уравнений Блэка–Шоулза и конвекции-диффузии с определением положения свободной границы
Джанбекова А. Р., Shvedov A. S., Математическое моделирование 2026 Т. 38 № 3 С. 159–176
Boundary value problems for the Black–Scholes partial differential equation, which describes the value of a financial instrument, may contain a free boundary condition if the financial instrument allows for early exercise. This article considers free boundary value problems for the Black–Scholes equation and the convection diffusion equation. For the convection diffusion equation, a finite difference ...
Added: June 20, 2026
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
Некоторые полные сложностные дихотомии для задачи о доминирующем множестве
Дахно Г. С., 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
  • 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