Logo BSU

Please use this identifier to cite or link to this item: https://elib.bsu.by/handle/123456789/258439
Title: Графы самопересечений замкнутых ломаных
Other Titles: Graphs of intersections of closed polygonal chains / N. P. Prochorov, E. N. Dul
Authors: Прохоров, Н. П.
Дуль, Е. Н.
Issue Date: 2021
Publisher: Минск : БГУ
Citation: Журнал Белорусского государственного университета. Математика. Информатика = Journal of the Belarusian State University. Mathematics and Informatics. - 2021. - № 1. - С. 54-68
Abstract: Введен и изучен такой подкласс струнных графов, как графы самопересечений замкнутых ломаных (класс CPC-графов). Указаны необходимые условия принадлежности графа к классу CPC, запрещенные подграфы данного класса, операции над графами, сохраняющие их принадлежность к классу CPC. Рассмотрен вопрос о существовании k-регулярных CPC-графов, в частности найдены пары (k, n) и приведены оценки на количество значений k, при которых существует k-регулярный граф на n вершинах, показано существование бесконечного числа k-регулярных CPC-графов для любого k ∈ . Исследованы алгоритмические вопросы в классе CPC-графов. Доказано, что задачи о доминирующем множестве, раскраске, независимости и наибольшем цикле в классе CPC-графов являются NP-трудными, а задача распознавания CPC-графов принадлежит к классу PSPACE.
Abstract (in another language): In the paper such subclass of string graphs as intersection graphs of closed polygonal chains (class of CPC-graphs) was considered, necessary conditions for belonging to that class, forbidden subgraphs and operations with graphs which preserve belonging to the CPC class were found. Considered question about the existence of k-regular CPC-graphs, par ticularly, pairs (k, n), such that there exists k-regular CPC-graph on n vertexes were found, proved that there are infinitely many k-regular CPC-graphs for any k ∈ , estimations for the number of k, such that k-regular graph on n vertexes exists, were given. Algorithmic questions in the class of CPC-graphs were investigated. It was proved that independent and dominating set problems, coloring problem and the problem about maximal cycle are NP-hard in the class of CPC-graphs, and problem of recognition of the CPC-graphs belongs to the PSPACE class.
URI: https://elib.bsu.by/handle/123456789/258439
ISSN: 1561-834X
DOI: 10.33581/2520-6508-2021-1-54-68
Licence: info:eu-repo/semantics/openAccess
Appears in Collections:2021, №1

Files in This Item:
File Description SizeFormat 
54-68.pdf1,43 MBAdobe PDFView/Open
Show full item record Google Scholar


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.