Opuscula Mathematica
Opuscula Math. 46, no. 5 (2026), 773-790

Independent mutual-visibility sets and distance edge-critical graphs

Jing Tian
Csilla Bujtás
Sandi Klavžar
Abstract. In this paper, connections between independent sets and the variety of mutual-visibility sets are studied. It is proved that every outer mutual-visibility set of a graph is independent if and only if the graph is distance edge-critical. Several constructions yielding distance edge-critical graphs are given. Graphs in which every independent set is a total mutual-visibility or a dual mutual-visibility set are characterized, as well as graphs in which every total mutual-visibility set is independent. Along the way the total mutual-visibility number of some graphs derived from fullerenes is determined. Diameter four graphs in which every independent set is a mutual-visibility set are characterized. It is proved that determining the maximum cardinality of an independent mutual-visibility set and deciding whether it equals the independence number of a graph are NP-hard problems, and the same is true for independent total, outer and dual mutual-visibility sets.
Keywords: mutual-visibility set, independent set, distance edge-critical graph, dense diamond graph, computational complexity.
Mathematics Subject Classification: 05C12, 05C69, 05C76, 68Q17.
Full text (pdf)
References ▼
  1. [1] M. Axenovich, D. Liu, Visibility in hypercubes, Graphs Combin. 42 (2026), 38. https://doi.org/10.1007/s00373-026-03025-9
  2. [2] B. Bollobás, On a conjecture of Erdős, Hajnal and Moon, Amer. Math. Monthly 74 (1967), 178-179. https://doi.org/10.2307/2315614
  3. [3] G. Boruzanlı Ekinci, Cs. Bujtás, Mutual-visibility problems in Kneser and Johnson graphs, Ars Math. Contemp. 25 (2025), #P3.07. https://doi.org/10.26493/1855-3974.3344.4c8
  4. [4] B. Brešar, I.G. Yero, Lower (total) mutual visibility in graphs, Appl. Math. Comput. 465 (2024), 128411. https://doi.org/10.1016/j.amc.2023.128411
  5. [5] Cs. Bujtás, S. Klavžar, J. Tian, Total mutual-visibility in Hamming graphs, Opuscula Math. 45 (2025), 63-78. https://doi.org/10.7494/opmath.2025.45.1.63
  6. [6] Cs. Bujtás, S. Klavžar, J. Tian, Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets, Aequationes Math. 99 (2025), 1883-1901. https://doi.org/10.1007/s00010-025-01197-y
  7. [7] S. Cicerone, A. Di Fonso, G. Di Stefano, A. Navarra, F. Piselli, Mutual and total mutual visibility in hypercube-like graphs, Appl. Math. Comput. 491 (2025), 129216. https://doi.org/10.1016/j.amc.2024.129216
  8. [8] S. Cicerone, G. Di Stefano, L. Drožđek, J. Hedžet, S. Klavžar, I.G. Yero, Variety of mutual-visibility problems in graphs, Theoret. Comput. Sci. 974 (2023), 114096. https://doi.org/10.1016/j.tcs.2023.114096
  9. [9] S. Cicerone, G. Di Stefano, S. Klavžar, On the mutual-visibility in Cartesian products and in triangle-free graphs, Appl. Math. Comput. 438 (2023), 127619. https://doi.org/10.1016/j.amc.2022.127619
  10. [10] S. Cicerone, G. Di Stefano, S. Klavžar, I.G. Yero, Mutual-visibility in strong products of graphs via total mutual-visibility, Discrete Appl. Math. 358 (2024), 136-146. https://doi.org/10.1016/j.dam.2024.06.038
  11. [11] S. Cicerone, G. Di Stefano, S. Klavžar, I.G. Yero, Mutual-visibility problems on graphs of diameter two, European J. Combin. 120 (2024), 103995.
  12. [12] J. Cooper, G. Tauscheck, Distance critical graphs, Graphs Combin. 41 (2025), 87. https://doi.org/10.1007/s00373-025-02943-4
  13. [13] M. Dettlaff, M. Lemańska, J.A. Rodríguez-Velázquez, I.G. Yero, Mobile mutual-visibility sets in graphs, Ars Math. Contemp. 26 (2026), #P1.10. https://doi.org/10.26493/1855-3974.3410.9bc
  14. [14] G. Di Stefano, Mutual visibility in graphs, Appl. Math. Comput. 419 (2022), 126850. https://doi.org/10.1016/j.amc.2021.126850
  15. [15] D. Ellis, M.-R. Ivan, I. Leader, Turán densities for daisies and hypercubes, Bull. Lond. Math. Soc. 56 (2024), 3838-3853.
  16. [16] P. Erdős, E. Howorka, An extremal problem in graph theory, Ars Combin. 9 (1980), 249-251.
  17. [17] M.R. Garey, D.S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, Freeman, San Francisco, CA, 1979.
  18. [18] R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, Boca Raton, FL, 2011.
  19. [19] M.A. Henning, J. Southey, A characterization of the non-trivial diameter two graphs of minimum size, Discrete Appl. Math. 187 (2015), 91-95. https://doi.org/10.1016/j.dam.2015.02.009
  20. [20] D. Korže, A. Vesel, Mutual-visibility sets in Cartesian products of paths and cycles, Results Math. 79 (2024), 116. https://doi.org/10.1007/s00025-024-02139-x
  21. [21] D. Korže, A. Vesel, Variety of mutual-visibility problems in hypercubes, Appl. Math. Comput. 491 (2025), 129218. https://doi.org/10.1016/j.amc.2024.129218
  22. [22] D. Kuziak, J.A. Rodríguez-Velázquez, Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products, Bull. Malays. Math. Sci. Soc. 46 (2023), 197. https://doi.org/10.1007/s40840-023-01590-3
  23. [23] D. Roy, S. Klavžar, A.S. Lakshmanan, Counting largest mutual-visibility and general position sets of glued \(t\)-ary trees, Results Math. 80 (2025), 207. https://doi.org/10.1007/s00025-025-02529-9
  24. [24] D. Roy, S. Klavžar, A.S. Lakshmanan, Mutual-visibility and general position in double graphs and in Mycielskians, Appl. Math. Comput. 488 (2025), 129131. https://doi.org/10.1016/j.amc.2024.129131
  25. [25] J. Tian, S. Klavžar, Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products, Discuss. Math. Graph Theory 44 (2024), 1277-1291. https://doi.org/10.7151/dmgt.2496
  26. [26] W. Wessel, Über eine Klasse paarer Graphen. I. Beweis einer Vermutung von Erdős, Hajnal und Moon, Wiss. Z. Tech. Hochsch. Ilmenau 12 (1966), 253-256.
About the authors ▼
Jing Tian
https://orcid.org/0000-0002-1578-4798
Zhejiang University of Science and Technology, School of Science, Hangzhou, Zhejiang 310023, P.R. China
Csilla Bujtás
https://orcid.org/0000-0002-0511-5291
University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
Sandi Klavžar (corresponding author)
https://orcid.org/0000-0002-1556-4744
University of Ljubljana, Faculty of Mathematics and Physics, Ljubljana, Slovenia; University of Maribor, Faculty of Natural Sciences and Mathematics, Maribor, Slovenia; Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia
About the article ▼
Communicated by Andrzej Żak.
Received: 2026-02-26.
Revised: 2026-09-07.
Accepted: 2026-09-09.
Published online: 2026-10-28.
Cite this article as ▼
Jing Tian, Csilla Bujtás, Sandi Klavžar, Independent mutual-visibility sets and distance edge-critical graphs, Opuscula Math. 46, no. 5 (2026), 773-790, https://doi.org/10.7494/OpMath.202609091.
Download this article's citation as: