Графы самопересечений замкнутых ломаных

  • Николай Петрович Прохоров Белорусский государственный университет, пр. Независимости 4, 220030, г. Минск, Беларусь https://orcid.org/0000-0001-9725-299X
  • Екатерина Николаевна Дуль Белорусский государственный университет, пр. Независимости 4, 220030, г. Минск, Беларусь https://orcid.org/0000-0001-9073-7855
DOI: https://doi.org/10.33581/2520-6508-2021-1-54-68

Аннотация

Введен и изучен такой подкласс струнных графов, как графы самопересечений замкнутых ломаных (класс CPC-графов). Указаны необходимые условия принадлежности графа к классу CPC, запрещенные подграфы данного класса, операции над графами, сохраняющие их принадлежность к классу CPC. Рассмотрен вопрос о существовании k-регулярных CPC-графов, в частности найдены пары (k, n) и приведены оценки на количество значений k, при которых существует k-регулярный граф на n вершинах, показано существование бесконечного числа k-регулярных CPC-графов для любого k∈N. Исследованы алгоритмические вопросы в классе CPC-графов. Доказано, что задачи о доминирующем множестве, раскраске, независимости и наибольшем цикле в классе CPC графов являются NP-трудными, а задача распознавания CPC-графов принадлежит к классу PSPACE.

Биографии авторов

Николай Петрович Прохоров, Белорусский государственный университет, пр. Независимости 4, 220030, г. Минск, Беларусь

магистрант кафедры дискретной математики и алгоритмики факультета прикладной математики и информатики. Научный руководитель – доктор физико-математических наук, доцент М. М. Васьковский

Екатерина Николаевна Дуль, Белорусский государственный университет, пр. Независимости 4, 220030, г. Минск, Беларусь

студентка факультета прикладной математики и информатики. Научный руководитель – М. М. Васьковский

Литература

  1. Sinden FW. Topology of thin film RC circuits. The Bell System Technical Journal. 1966;45(9):1639–1662. DOI: 10.1002/ j.1538-7305.1966.tb01713.x.
  2. Ehrlich G, Even S, Tarjan RE. Intersection graphs of curves in the plane. Journal of Combinatorial Theory. Series B. 1976; 21(1):8–20. DOI: 10.1016/0095-8956(76)90022-8.
  3. Chalopin J, Gonçalves D. Every planar graph is the intersection graph of segments in the plane: extended abstract. In: Proceedings of the Forty-first annual ACM symposium on theory of computing; 2009 May 31 – June 2; Bethesda, Maryland, USA. New York: Association for Computing Machinery; 2009. p. 631–638. DOI: 10.1145/1536414.1536500.
  4. Kratochvíl J, Matoušek J. Intersection graphs of segments. Journal of Combinatorial Theory. Series B. 1994;62(2):289–315. DOI: 10.1006/jctb.1994.1071.
  5. Kratochvíl J. String graphs. II. Recognizing string graphs is NP-hard. Journal of Combinatorial Theory. Series B. 1991;52(1):67–78. DOI: 10.1016/0095-8956(91)90091-W.
  6. Ore O. Graphs and their uses. New York: Random House; 1963. VIII, 131 p. Russian edition: Ore O. Grafy i ikh primenenie. Golovina LI, translator; Yaglom IM, editor. Moscow: Mir; 1965. 174 p.
  7. Kratochvíl J. String graphs. I. The number of critical nonstring graphs is infinite. Journal of Combinatorial Theory. Series B. 1991;52(1):53–66. DOI: 10.1016/0095-8956(91)90090-7.
  8. Dangelmayr C. Intersection graphs of pseudosegments [dissertation]. Berlin: Freien Universität Berlin; 2010. 136 p.
  9. Fuks DB. [Selfintersections of closed polygonal chains]. Kvant. 1988;1:30–34. Russian.
  10. Keil JM. The complexity of domination problems in circle graphs. Discrete Applied Mathematics. 1993;42(1):51–63. DOI: 10.1016/0166-218X(93)90178-Q.
  11. Unger W. On the k-colouring of circle-graphs. In: Cori R, Wirsing M, editors. STACS 88. 5th Annual symposium on theoretical aspects of computer science; 1988 February 11–13; Bordeaux, France. Berlin: Springer-Verlag; 1988. p. 61–72. (Lecture Notes in Computer Science; volume 294).
  12. Damaschke P. The Hamiltonian circuit problem for circle graphs is NP-complete. Information Processing Letters. 1989;32(1): 1–2. DOI: 10.1016/0020-0190(89)90059-8.
  13. Garey MR, Johnson DS. Computers and intractability. A guide to the theory of NP-completeness. New York: W. H. Freeman and Company; 1979. X, 338 p.
  14. Valiant LG. Universality considerations in VLSI circuits. IEEE Transactions on Computers. 1981;C-30(2):135–140. DOI: 10.1109/TC.1981.6312176.
  15. Renegar J. On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals. Journal of Symbolic Computation. 1992;13(3):255–299. DOI: 10.1016/S0747-7171(10)80003-3.
  16. Pilz A, Welzl E. Order on order types. In: Arge L, Pach J, editors. 31st International symposium on computational geometry (SoCG’2015); 2015 June 22–25; Eindhoven, The Netherlands. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2015. p. 285–299. (LIPIcs; volume 34). DOI: 10.4230/LIPIcs.SOCG.2015.285.
  17. Goodman JE, Pollack R, Sturmfels B. The intrinsic spread of a configuration in Rd. Journal of the American Mathematical Society. 1990;3(3):639–651. DOI: 10.1090/S0894-0347-1990-1046181-2.
Опубликован
2021-04-12
Ключевые слова: граф пересечений, граф самопересечений замкнутой ломаной, регулярный граф, NP-полнота, полиномиальная сводимость
Как цитировать
Прохоров, Н. П., & Дуль, Е. Н. (2021). Графы самопересечений замкнутых ломаных. Журнал Белорусского государственного университета. Математика. Информатика, 1, 54-68. https://doi.org/10.33581/2520-6508-2021-1-54-68
Выпуск
№ 1 (2021): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Copyright (c) 2021 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).