Discrete mathematics and Mathematical cybernetics
Graphs of intersections of closed polygonal chains
N. P. Prochorov,
E. N. Dul Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus
Abstract:
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\in \mathbb{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.
Keywords:
intersection graph; intersection graph of closed polygonal chains; regular graph; $NP$-completeness; polynomial-time reduction.
UDC:
519.172.4+
519.178 Received: 08.09.2020
DOI:
10.33581/2520-6508-2021-1-54-68