On well ve-covered and well ev‑covered graphs

Authors

  • Yury L. Orlovich Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus
  • Mikita A. Shutro Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

Keywords:

graph, independent vе‑dominating set, independent ev‑dominating set, well vе‑covered graph, well ev‑covered graph, hereditary graph class, NP-completeness

Abstract

In this paper, the classes of well vе-covered graphs and well ev-covered graphs are investigated. A graph is called well vе-covered (well ev-covered, respectively) if all its minimal independent vе-dominating (minimal independent ev-dominating, respectively) sets have the same cardinality. It is shown that the problems of recognising the graph classes under consideration are co-NP-complete even for some restrictions of these classes. Characterisations, in terms of forbidden induced subgraphs, for the maximal hereditary subclasses of well vе-covered graphs and well ev-covered graphs are found. The computational complexity of problems related to minimum independent vе-dominating and minimum independent ev-dominating sets is established.

Author Biographies

  • Yury L. Orlovich, Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

    PhD (physics and mathematics), docent; dean of the faculty of applied mathematics and computer science

  • Mikita A. Shutro, Belarusian State University, 4 Niezaliezhnasci Avenue, Minsk 220030, Belarus

    student at the faculty of applied mathematics and computer science

References

  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.

Downloads

Additional Files

Published

2026-05-22

Issue

No. 1 (2026): Journal of the Belarusian State University. Mathematics and Informatics

Section

Discrete Mathematics and Mathematical Cybernetics

License

Copyright (c) 2026 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)

How to Cite

[1]
Orlovich, Y.L. and Shutro, M. 2026. On well ve-covered and well ev‑covered graphs. Journal of the Belarusian State University. Mathematics and Informatics. 1 (May 2026), 94–107.