Graphs of intersections of closed polygonal chains
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 questi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Belarusian |
| Published: |
Belarusian State University
2021-04-01
|
| Series: | Журнал Белорусского государственного университета: Математика, информатика |
| Subjects: | |
| Online Access: | https://journals.bsu.by/index.php/mathematics/article/view/3379 |
| _version_ | 1819282186248912896 |
|---|---|
| author | Nikolai P. Prochorov Ekaterina N. Dul |
| author_facet | Nikolai P. Prochorov Ekaterina N. Dul |
| author_sort | Nikolai P. Prochorov |
| collection | DOAJ |
| description | 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, particularly, 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 ∈ N, 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. |
| first_indexed | 2024-12-24T01:11:35Z |
| format | Article |
| id | doaj.art-afaf53c7b7e34c0ab0be3c74a03baa18 |
| institution | Directory Open Access Journal |
| issn | 2520-6508 2617-3956 |
| language | Belarusian |
| last_indexed | 2024-12-24T01:11:35Z |
| publishDate | 2021-04-01 |
| publisher | Belarusian State University |
| record_format | Article |
| series | Журнал Белорусского государственного университета: Математика, информатика |
| spelling | doaj.art-afaf53c7b7e34c0ab0be3c74a03baa182022-12-21T17:22:57ZbelBelarusian State UniversityЖурнал Белорусского государственного университета: Математика, информатика2520-65082617-39562021-04-011546810.33581/2520-6508-2021-1-54-683379Graphs of intersections of closed polygonal chainsNikolai P. Prochorov0https://orcid.org/0000-0001-9725-299XEkaterina N. Dul1https://orcid.org/0000-0001-9073-7855Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, BelarusBelarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, BelarusIn 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, particularly, 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 ∈ N, 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.https://journals.bsu.by/index.php/mathematics/article/view/3379intersection graphintersection graph of closed polygonal chainsregular graphnp-completenesspolynomial-time reduction |
| spellingShingle | Nikolai P. Prochorov Ekaterina N. Dul Graphs of intersections of closed polygonal chains Журнал Белорусского государственного университета: Математика, информатика intersection graph intersection graph of closed polygonal chains regular graph np-completeness polynomial-time reduction |
| title | Graphs of intersections of closed polygonal chains |
| title_full | Graphs of intersections of closed polygonal chains |
| title_fullStr | Graphs of intersections of closed polygonal chains |
| title_full_unstemmed | Graphs of intersections of closed polygonal chains |
| title_short | Graphs of intersections of closed polygonal chains |
| title_sort | graphs of intersections of closed polygonal chains |
| topic | intersection graph intersection graph of closed polygonal chains regular graph np-completeness polynomial-time reduction |
| url | https://journals.bsu.by/index.php/mathematics/article/view/3379 |
| work_keys_str_mv | AT nikolaipprochorov graphsofintersectionsofclosedpolygonalchains AT ekaterinandul graphsofintersectionsofclosedpolygonalchains |