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: | Прохоров, Н. П. Дуль, Е. Н. |
| Keywords: | ЭБ БГУ::ЕСТЕСТВЕННЫЕ И ТОЧНЫЕ НАУКИ::Математика |
| 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 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.