TY  - JOUR
ID  - Tian2026
LB  - Tian2026
AU  - Tian, Jing
AU  - Bujtás, Csilla
AU  - Klavžar, Sandi
TI  - Independent mutual-visibility sets and distance edge-critical graphs
ST  - Independent mutual-visibility sets and distance edge-critical graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2026
VL  - 46
IS  - 5
SP  - 773
EP  - 790
DO  - https://doi.org/10.7494/OpMath.202609091
UR  - https://doi.org/10.7494/OpMath.202609091
AB  - 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.
KW  - mutual-visibility set
KW  - independent set
KW  - distance edge-critical graph
KW  - dense diamond graph
KW  - computational complexity
SN  - 1232-9274
ER  -