О хорошо ve-укрытых и хорошо ev-укрытых графах

Авторы

  • Юрий Леонидович Орлович Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь
  • Никита Алексеевич Шутро Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

Ключевые слова:

граф, независимое vе‑доминирующее множество, независимое ev‑доминирующее множество, хорошо vе‑укрытый граф, хорошо ev‑укрытый граф, наследственный класс графов, NP-полнота

Аннотация

Исследуются классы хорошо vе‑укрытых графов и хорошо ev‑укрытых графов. Граф называется хорошо vе‑укрытым (соответственно хорошо ev‑укрытым), если все его независимые минимальные vе‑доминирующие (соответственно независимые минимальные ev‑доминирующие) множества имеют одинаковую мощность. Показано, что задачи распознавания рассматриваемых классов графов являются co-NP-полными даже для некоторых сужений этих классов. Найдены характеризации в терминах запрещенных порожденных подграфов для максимальных наследственных подклассов хорошо vе‑укрытых графов и хорошо ev‑укрытых графов. Установлена вычислительная сложность задач, связанных с наименьшими независимыми vе‑доминирующими и наименьшими независимыми ev‑доминирующими множествами.

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

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

    кандидат физико-математических наук, доцент; декан факультета прикладной математики и информатики

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

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

Библиографические ссылки

  1. Bondy JA, Murty USR. Graph theory. Berlin: Springer; 2008. XII, 651 p. (Graduate texts in mathematics; volume 244).
  2. Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. San Francisco: W. H. Freeman and Company; 1979. XII, 338 p.
  3. Haynes T, Hedetniemi ST, Henning MA. Domination in graphs: core concepts. Cham: Springer; 2023. XX, 644 p. (Springer monographs in mathematics). DOI: 10.1007/978-3-031-09496-5.
  4. Plummer MD. Some covering concepts in graphs. Journal of Combinatorial Theory. 1970;8(1):91–98. DOI: 10.1016/S0021-9800(70)80011-4.
  5. Chvátal V, Slater PJ. A note on well-covered graphs. Annals of Discrete Mathematics. 1993;55:179–181. DOI: 10.1016/S0167-5060(08)70387-X.
  6. Sankaranarayana RS, Stewart LK. Complexity results for well-covered graphs. Networks. 1992;22(3):247–262. DOI: 10.1002/net.3230220304.
  7. Caro Y, Sebö A, Tarsi M. Recognizing greedy structures. Journal of Algorithms. 1996;20(1):137–156. DOI: 10.1006/jagm.1996.0006.
  8. Brown J, Hoshino R. Well-covered circulant graphs. Discrete Mathematics. 2011;311(4):244–251. DOI: 10.1016/j.disc.2010.11.007.
  9. Baptiste P, Kovalyov MY, Orlovich YuL, Werner F, Zverovich IE. Graphs with maximal induced matchings of the same size. Discrete Applied Mathematics. 2017;216(part 1):15–28. DOI: 10.1016/j.dam.2016.08.015.
  10. Tankus D, Tarsi M. Well-covered claw-free graphs. Journal of Combinatorial Theory. Series B. 1996;66(2):293–302. DOI: 10.1006/jctb.1996.0022.
  11. Tankus D, Tarsi M. The structure of well-covered graphs and the complexity of their recognition problems. Journal of Combinatorial Theory. Series B. 1997;69(2):230–233. DOI: 10.1006/jctb.1996.1742.
  12. Finbow A, Hartnell B, Nowakowski RJ. A characterization of well-covered graphs of girth 5 or greater. Journal of Combinatorial Theory. Series B. 1993;57(1):44–68. DOI: 10.1006/jctb.1993.1005.
  13. Finbow A, Hartnell B, Nowakowski RJ. A characterization of well-covered graphs that contain neither 4- nor 5-cycles. Journal of Graph Theory. 1994;18(7):713–721. DOI: 10.1002/jgt.3190180707.
  14. Caro Y, Ellingham MN, Ramey JE. Local structure when all maximal independent sets have equal weight. SIAM Journal on Discrete Mathematics. 1998;11(4):644–654. DOI: 10.1137/S0895480196300479.
  15. Prisner E, Topp J, Vestergaard PD. Well-covered simplicial, chordal, and circular arc graphs. Journal of Graph Theory. 1996;21(2):113–119. DOI: 10.1002/(SICI)1097-0118(199602)21:2<113::AID-JGT1>3.0.CO;2-U.
  16. Peters KW. Theoretical and algorithmic results on domination and connectivity [dissertation]. Clemson: Clemson University; 1986. IX, 162 p.
  17. Lewis JR. Vertex-edge and edge-vertex domination in graphs [dissertation]. Clemson: Clemson University; 2007. XVI, 82 p.
  18. Lewis JR, Hedetniemi ST, Haynes TW, Fricke GH. Vertex-edge domination. Utilitas Mathematica. 2010;81:193–213.
  19. Jamieson AC. Linear algorithms for edge-vertex domination in trees. Congressus Numerantium. 2007;187:214–222.
  20. Boutrig R, Chellali M, Haynes TW, Hedetniemi ST. Vertex-edge domination in graphs. Aequationes mathematicae. 2016;90(2):355–366. DOI: 10.1007/s00010-015-0354-2.
  21. Boutrig R, Chellali M, Meddah N. Well vе‑covered graphs. Communications in Combinatorics and Optimization. 2025;10(1):69–78.
  22. Boutrig R, Chellali M. Well ev‑covered trees. RAIRO – Operations Research. 2023;57(3):1481–1489. DOI: 10.1051/ro/2023088.
  23. Chellali M. Further results on independent edge-vertex domination. Discrete Mathematics, Algorithms and Applications. 2024;16(6):2350080. DOI: 10.1142/S1793830923500805.
  24. Kitaev S, Lozin V. Words and graphs. Cham: Springer; 2015. XVIII, 264 p. (Monographs in theoretical computer science). DOI: 10.1007/978-3-319-25859-1.
  25. Dabrowski K, Lozin VV, Zamaraev V. On factorial properties of chordal bipartite graphs. Discrete Mathematics. 2012;312(16):2457–2465. DOI: 10.1016/j.disc.2012.04.010.
  26. Haynes TW, Slater PJ. Paired-domination and the paired-domatic number. Congressus Numerantium. 1995;109:65–72.
  27. Haynes TW, Slater PJ. Paired-domination in graphs. Networks. 1998;32(3):199–206. DOI: 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F.
  28. Desormeaux WJ, Haynes TW, Henning MA. Paired domination in graphs. In: Haynes TW, Hedetniemi ST, Henning MA, editors. Topics in domination in graphs. Cham: Springer; 2020. p. 31–77 (Developments in mathematics; volume 64). DOI: 10.1007/978-3-030-51117-3_3.
  29. Edwards M. Criticality concepts for paired domination in graphs [dissertation]. Victoria: University of Victoria; 2006. VIII, 75 p.
  30. Fitzpatrick SL, Hartnell BL. Well paired-dominated graphs. Journal of Combinatorial Optimization. 2010;20(2):194–204. DOI: 10.1007/s10878-008-9203-8.
  31. Lawler E. Combinatorial optimization: networks and matroids. Mineola: Dover Publications; 2001. X, 374 p.

Загрузки

Дополнительные файлы

Опубликован

2026-05-22

Выпуск

№ 1 (2026): Журнал Белорусского государственного университета. Математика. Информатика

Раздел

Дискретная математика и математическая кибернетика

Лицензия

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

Лицензия 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).

Как цитировать

[1]
Орлович, Ю.Л. и Шутро, Н.А. 2026. О хорошо ve-укрытых и хорошо ev-укрытых графах. Журнал Белорусского государственного университета. Математика. Информатика. 1 (май 2026), 94–107.