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. Graphs in which every independent set is a mutual-visibility set are discussed and characterized over diameter four graphs. 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 AMS Math. Subj. Class. (2020) : 05C12, 05C69, 05C76, 68Q17 1 Introduction The mutual-visibility problem was in 2022 transferred from computer science to graph theory in Di Stefano’s paper [ 14 ] . The problem immediately attracted widespread interest, in part because it is closely related to several other important mathematical topics. Let us emphasize its connections to Turán type problems [ 3 , 5 , 11 ] , to the famous open Zarankiewicz problem [ 9 ] , and to the Bollobás-Wessel theorem [ 2 , 26 ] , see [ 4 ] . Moreover, to prove that there exist large mutual-visibility sets in hypercubes, Axenovich and Liu [ 1 ] applied a recent breakthrough result on daisy-free hypergraphs due to Ellis, Ivan, and Leader [ 15 ] . From among other papers on graph mutual-visibility we highlight [ 7 , 13 , 20 , 21 , 22 , 23 , 24 , 25 ] . While investigating mutual-visibility in strong products [ 10 ] , the need for the total mutual-visibility concept appeared. The whole variety was later (although published earlier) introduced in [ 8 ] as follows. If X is a subset of vertices of a graph G , then u,v\in V(G) are X -visible , if there exists a shortest u,v -path P such that V(P)\cap X\subseteq\{u,v\} . If every two vertices from X are X -visible, then X is a mutual-visibility set ( MV set for short), and if any two vertices from V(G) are X -visible, then X is a total mutual-visibility set ( total MV set ). Further, if any two vertices from X and any two vertices from \overline{X} are X -visible, then X is a dual mutual-visibility set ( dual MV set ), and if any two vertices from X are X -visible, and any two vertices x\in X , y\in\overline{X} are X -visible, then X is an outer mutual-visibility set ( outer MV set ). ( \overline{X} stands for V(G)\setminus X .) The cardinality of a largest MV set (resp. total/dual/outer MV set) is the mutual-visibility number (resp. total/dual/outer mutual-visibility number ) \mu(G) (resp. \mut(G) , \mud(G) , \muo(G) ) of G . To derive general bounds for the mutual-visibility number in Cartesian products [ 9 ] , independent MV sets were introduced as those MV sets which induce edgeless graphs. Next, Korže and Vesel [ 21 , Proposition 3.8] proved that if d\geq 1 , then \mut(Q_{d})=2\alpha(Q_{d}^{\prime}) , where Q_{d}^{\prime} is the dual cube of dimension d , and \alpha(\cdot) stands for the independence number. The following result intrigued us further, where g(G) denotes the girth of a graph G . Proposition 1.1 [ 11 , Lemma 5.2] If G is a connected graph of order at least 3 and with g(G)\geq 5 , then every outer MV set of G is independent. In view of this proposition and other mentioned results, we set ourselves the task of systematically reviewing when all independent sets occur to be MV sets and the other way around. After some preparation in the next section, we consider outer mutual-visibility in Section 3 . We prove that every outer MV set of a graph is independent if and only if the graph is distance edge-critical. We also provide several constructions yielding distance edge-critical graphs, and consider the graphs in which every independent set is an outer MV set. In Section 4 we prove that the so-called dense diamond graphs characterize the graphs in which every independent set is a total MV or a dual MV set for that matter. We also characterize graphs in which every total MV set is independent, and provide a partial description of graphs in which every dual MV set is independent. Along the way we determine the total mutual-visibility number of some graphs derived from fullerenes. In Section 5 we first describe graphs in which every independent set is a MV set as the graphs which contain no independent, strong critical set. Then we give a polynomial-time characterization of such graphs among diameter four graphs, and use the strong product to construct graphs of an arbitrarily large diameter in which every independent set is a MV set. In Section 6 we prove 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 over the class of graphs of diameter d for every fixed d\geq 4 , and that the same is true for independent total, outer and dual mutual-visibility sets. We conclude the paper by proposing several open problems. 2 Preliminaries Let n(G) and m(G) respectively denote the order and the size of a graph G . For vertices u and v of G , the length of a shortest u,v -path is the distance between u and v and denoted by d_{G}(u,v) . The interval I_{G}[u,v] is the set of vertices which lie on shortest u,v -paths in G . The diameter \diam(G) of G is the length of a longest shortest path in G . A subgraph H of G is convex , if for every two vertices of H , all shortest u,v -paths belong to H . A set S\subset V(G) of G is distance \{u,v\} -critical , if u,v\in V(G)\setminus S and d_{G-S}(u,v)>d_{G}(u,v) . In the case when S=\{x\} we say that x is a distance critical vertex . Similarly, an edge xy is distance critical , if there exist vertices u,v\in V(G) , where \{u,v\}\neq\{x,y\} , such that d_{G-xy}(u,v)>d_{G}(u,v) . Further, G is distance vertex-critical if every vertex of G is distance critical and is distance edge-critical if every edge of G is distance critical. Since this will be the only type of criticality considered in this paper, we will simplify the terminology to critical set , critical vertex , critical edge , vertex-critical graph , and edge-critical graph . The first statement of the following lemma can be found in [ 16 , Theorem 1] . In this paper by Erdős and Howorka, where vertex-critical graphs were introduced, the focus was on the largest number of edges such a graph can contain. As far as we know, nothing followed in this direction for almost half of a century, until these graphs were systematically researched for the first time in the recent paper [ 12 ] . Lemma 2.1 If G is a connected graph, then the following hold. (i) G is vertex-critical if and only if every vertex of G is the middle vertex of a convex P_{3} [ 16 ] . (ii) G is edge-critical if and only if every edge of G lies on a convex P_{3} . Proof. We only need to prove (ii). Assume first that every edge of G lies on a convex P_{3} and let e=uv be an arbitrary edge. Let uvw be a convex P_{3} containing e . Then d_{G-e}(u,w)\geq 3 , meaning that e is a critical edge. Since this conclusion holds for every edge, G is edge-critical. Assume second that G is an edge-critical graph and let e=uv be an arbitrary edge of G . Let x and y be vertices such that d_{G-e}(x,y)>d_{G}(x,y) , where \{x,y\}\neq\{u,v\} . This means that every shortest x,y -path in G contains e . Consider an arbitrary shortest x,y -path P . Then P contains a subpath P^{\prime}=uvw or wuv . Since every shortest x,y -path contains e=uv , the subpath P^{\prime} is a convex P_{3} containing e . \square The sets of vertex-critical and edge-critical graphs are incomparable. For instance, the graph obtained from C_{4} by attaching a pendant vertex to two of its non-adjacent vertices is edge-critical but not vertex-critical. On the other hand, the Wagner graph (as shown in Fig. 1 ) is vertex-critical but not edge-critical. Figure 1: Wagner graph M_{8} Let G and H be disjoint graphs. Then the join G\vee H is the graph obtained from the disjoint union of G and H by adding the edge gh for every g\in V(G) and every h\in V(H) . Further, when we say that X is a join graph , we mean that X can be represented as G\vee H . The Cartesian product G\,\square\,H has the vertex set V(G)\times V(H) , vertices (g,h) and (g^{\prime},h^{\prime}) being adjacent if either g=g^{\prime} and hh^{\prime}\in E(H) , or h=h^{\prime} and gg^{\prime}\in E(G) . The strong product G\boxtimes H has the vertex set V(G\boxtimes H)=V(G)\times V(H) and E(G\boxtimes H)=E(G\,\square\,H)\cup\{\{(g,h),(g^{\prime},h^{\prime})\}:gg^{\prime}\in E(G)\ {\rm and}\ hh^{\prime}\in E(H)\} . The subgraph of G\,\square\,H (resp., G\boxtimes H ) induced by the vertices (g,h) , g\in V(G) , is called a G -layer of G\,\square\,H (resp., G\boxtimes H ) and is denoted by G^{h} . For a vertex g\in G , the H -layer {}^{g}H is defined analogously. Note that G^{h}\cong G and {}^{g}H\cong H . To conclude the preliminaries, we recall the following result needed later on. Theorem 2.2 [ 6 , Theorem 5.2] If G is a connected graph and X\subseteq V(G) , then the following statements are equivalent. (i) X is a total MV set of G . (ii) Any two vertices u and v of G with d_{G}(u,v)=2 are X -visible. (iii) Any two vertices u and v of G with d_{G}(u,v)=2 satisfy N_{G}(u)\cap N_{G}(v)\not\subseteq X . 3 Outer mutual-visibility and independence As already mentioned, Proposition 1.1 was one of our main motivations for the present investigation. We now extend this results. Theorem 3.1 If G is a connected graph of order at least three, then the following statements are equivalent. (i) Every outer MV set of G is independent. (ii) G is an edge-critical graph. Proof. (i) \Rightarrow (ii): Let uv be an edge of G . By (i), the set X=\{u,v\} is not an outer MV set in G . As u and v are X -visible, there exists a vertex z\in V(G)\setminus X such that a vertex from X and z are not X -visible. Without loss of generality, we may suppose that every shortest u,z -path contains v . Then, if uvv^{\prime}\dots z is a shortest u,z -path, then uvv^{\prime} is a convex P_{3} . Since this happens for every edge of G , Lemma 2.1 (ii) implies that G is an edge-critical graph. (ii) \Rightarrow (i): Let X be an outer MV set of G and suppose on the contrary that X contains adjacent vertices u and v . Since G is an edge-critical graph, by Lemma 2.1 (ii) there exists a vertex w such that, without loss of generality, uvw is a convex P_{3} . Then u and w are not X -visible, which is a contradiction no matter whether w\in X or w\notin X . \square Restricting to graphs of diameter two, Theorem 3.1 further strengthens as follows. Proposition 3.2 If G is a graph with \diam(G)=2 , then every independent set is an outer MV set. In addition, if G is edge-critical, then outer MV sets coincide with independent sets and \muo(G)=\alpha(G) . Proof. Let S be an independent set of a graph G , where \diam(G)=2 . Then every two vertices of S are clearly S -visible. Moreover, if x\in S and y\notin S , then either xy\in E(G) or d_{G}(x,y)=2 . In any case, since S is independent, x and y are also S -visible. Assume next that G is also edge-critical. Then by Theorem 3.1 , every outer MV set is independent and we are done. \square Note that the Wagner graph M_{8} from Fig. 1 is an example of a diameter two graph which is not edge-critical and hence not every outer MV set of M_{8} is independent. 3.1 Edge-critical graphs In view of Theorem 3.1 and Proposition 3.2 , edge-critical graphs deserve a closer attention. Examples of edge-critical graphs include graphs G with g(G)\geq 5 and trees of order at least three. In addition, if G is an edge-critical graph, then every graph obtained from G by subdividing every edge of G arbitrary number of times (possibly zero) is also an edge-critical graph. Among the Cartesian product graphs, edge-critical graphs are characterized as follows. Proposition 3.3 If G and H are graphs, then G\,\square\,H is edge-critical if and only if both G and H are edge-critical. Proof. Assume first that G\,\square\,H is edge-critical. Let e=(g,h)(g^{\prime},h)\in E(G\,\square\,H) . Then by Lemma 2.1 (ii), e lies in a convex P_{3} of G\,\square\,H . By the structure of G\,\square\,H , this convex P_{3} must lie in the layer G^{h} . This in turn implies that gg^{\prime}\in E(G) lies in a convex P_{3} in G . So G is an edge-critical graph, and by the commutativity of the Cartesian product, H is an edge-critical graph as well. Conversely, assume that G and H are edge-critical graphs. Then using the fact that the layers of G\,\square\,H are convex subgraphs, and every edge of G\,\square\,H lies in some layer, we can conclude that G\,\square\,H is an edge-critical graph. \square Also among graphs of diameter two, the variety of edge-critical graphs remains large as illustrated by the following three families of such graphs. • K_{1,n} , n\geq 2 . • Let \mathcal{G} be a family of graphs introduced in [ 19 ] as follows. Let P be the Petersen graph, and let G_{7} be the graph obtained from the cycle C_{3} by adding a pendant edge to each vertex of the cycle and then adding a new vertex and joining it to the three degree-one vertices, see Fig. 2 . Then the family \mathcal{G} (i) contains C_{5} , G_{7} , and P ; and (ii) is closed under degree-two vertex duplication (see Fig. 2 again). It is straightforward to verify that every G\in\mathcal{G} is an edge-critical graph with \diam(G)=2 . For instance, in G_{7} we infer that every edge lies in a convex P_{3} such that its middle vertex is not of degree 2 . This implies that after a degree-two vertex duplication is performed, the constructed graph remains edge-critical. • The graph H_{n,m} , n\geq 3 , m\geq 1 , is defined as follows. Let A and B be the two bipartition sets of K_{n,m} , where |A|=n and |B|=m . Then H_{n,m} is obtained from the disjoint union of K_{n,m} and K_{n} by adding a matching between the vertices of K_{n} and the vertices of A . See Fig. 2 where H_{4,2} is shown and note that H_{3,1}=G_{7} . It is again straightforward to verify that every H_{n,m} is an edge-critical graph of diameter two. Moreover, every graph obtained from H_{n,1} by a degree-two vertex duplication is edge-critical and of diameter two. G_{7}\cong H_{3,1} H_{4,2} Figure 2: From left to right: G_{7}\cong H_{3,1} ; the graph obtained from G_{7} by duplicating once each of its degree two vertices; H_{4,2} If G is an edge-critical graph with \diam(G)=2 and has a leaf, then we can infer that G must be a star. For triangle-free edge-critical graphs G with \diam(G)=2 and \delta(G)\geq 2 we have the following structural result. Proposition 3.4 If G is a triangle-free, edge-critical graph with \diam(G)=2 and \delta(G)\geq 2 , then every edge of G lies in an induced 5 -cycle. Proof. Let e=xy\in E(G) . Since G is edge-critical, by Lemma 2.1 (ii) we may without loss of generality assume that there exists a neighbor x^{\prime} of x such that the vertices x^{\prime},x,y induce a convex P_{3} . Since \delta(G)\geq 2 , the vertex y has a neighbor y^{\prime}\neq x . Since G is triangle-free, y^{\prime}\neq x^{\prime} . Thus the vertices x^{\prime},x,y,y^{\prime} are pairwise different and lie on a P_{4} . Moreover, this P_{4} is induced since the presence of the edge x^{\prime}y^{\prime} would imply that x^{\prime},x,y would not induce a convex P_{3} . It follows, having in mind that \diam(G)=2 , that there exists a new vertex z such that x^{\prime}z,zy^{\prime}\in E(G) . The triangle-freeness of G also gives zx\notin E(G) and zy\notin E(G) . We can conclude that xx^{\prime}zy^{\prime}yx is an induced C_{5} containing the edge e . \square The graph obtained from C_{5} by duplicating one of its vertices is a graph that fulfills all the assumptions of Proposition 3.4 , yet it contains no convex C_{5} . Therefore, we cannot strengthen Proposition 3.4 by stating that every edge of G lies in a convex C_{5} . The following example shows that triangle-freeness cannot be omitted in Proposition 3.4 . We take a 6 -cycle v_{1}\dots v_{6}v_{1} and add the edges v_{1}v_{3} and v_{1}v_{5} . For the graph G obtained this way, \diam(G)=2 and \delta(G)\geq 2 . We can also identify convex P_{3} -subgraphs in G that together cover the entire edge set. Since N[v_{6}]\cap N[v_{2}]=\{v_{1}\} , the path v_{6}v_{1}v_{2} is convex. Similarly, v_{2}v_{3}v_{4} , v_{4}v_{5}v_{6} , v_{5}v_{1}v_{2} , and v_{3}v_{1}v_{6} are all convex P_{3} -subgraphs. Therefore G is edge-critical. On the other hand, there is no induced 5 -cycle in G . 4 Total/dual mutual-visibility and independence In this section we consider connections between independent sets, and total MV sets and dual MV sets. The graph K_{4}-e is known as the diamond graph. We say that a connected graph G is a dense diamond graph , if any two vertices u,v\in V(G) with d_{G}(u,v)=2 lie on a common diamond. Theorem 4.1 If G is a connected graph, then the following statements are equivalent. (i) Every independent set of G is a total MV set. (ii) Every independent set of G is a dual MV set. (iii) G is a dense diamond graph. Proof. (i) \Rightarrow (ii): This holds since total MV sets are dual MV sets. (ii) \Rightarrow (iii): Let x,y\in V(G) be vertices with d_{G}(x,y)=2 . Then W=N_{G}(x)\cap N_{G}(y) is not empty. If there exist adjacent vertices a,b\in W , then x,y,a,b induce a diamond. Otherwise, W induces an independent set. By the condition (ii), W must be a dual MV set. But this is not true because x and y are not W -visible. (iii) \Rightarrow (i): Let G be a dense diamond graph and let X be an independent set of G . We need to show that X is a total MV set. By Theorem 2.2 it suffices to demonstrate that if x,y\in V(G) with d_{G}(x,y)=2 , then x and y are X -visible. By (iii), there exists a subgraph K_{4}-e which contains x and y , let a and b be the common neighbors of x and y in this diamond. As ab\in E(G) we have |X\cap\{a,b\}|\leq 1 . It follows that x and y are X -visible. \square Consider the simple example of C_{4} to see that the equivalence in Theorem 4.1 does not remain true if we require that every independent set is a MV set or that it is an outer MV set. We can also characterize graphs with the reverse property for total MV sets. A convex diamond v_{1}v_{2}v_{3}v_{4} is a diamond where v_{1} and v_{3} are nonadjacent vertices and N(v_{1})\cap N(v_{3})=\{v_{2},v_{4}\}. With the same notation, v_{2}v_{4} is the middle edge of the diamond . Theorem 4.2 The following statements are equivalent for every connected graph G . (i) Every total MV set of G is independent. (ii) For every edge uv\in E(G) one of the following properties is true: (a) u or v is the middle vertex of a convex P_{3} ; (b) uv is the middle edge of a convex diamond. Proof. (i) \Rightarrow (ii): Assume that every total MV set of G is independent and consider an arbitrary edge uv\in E(G) . If u or v is the middle vertex of a convex P_{3} , then there is nothing to prove, hence assume that neither u nor v is the middle vertex of a convex P_{3} . We need to prove that uv is the middle edge of a convex diamond. As we have assumed that total MV sets are independent, X=\{u,v\} is not a total MV set. Hence there exist two vertices x and y which are not X -visible. Consider the following two cases. Case 1 : \{x,y\}\cap\{u,v\}\neq\emptyset . Assume without loss of generality that x=u . As u and v are X -visible, we then have y\neq v . Consider an arbitrary shortest y,x -path Q . Since x=u and y are not X -visible, v lies on Q . Let y^{\prime} be the neighbor of v on Q different from x ; it is possible that y^{\prime}=y . As Q is a shortest path, we clearly have y^{\prime}x\notin E(G) . Therefore, since v is not the middle vertex of a convex P_{3} , there exists a path y^{\prime}v^{\prime}x , where v^{\prime}\neq v . But this means that y and x are X -visible, a contradiction. Hence Case 1 never happens. Case 2 : \{x,y\}\cap\{u,v\}=\emptyset . Let Q be an arbitrary shortest x,y -path. In the first subcase suppose that Q contains the edge uv , and assume without loss of generality that d_{G}(x,u)d_{G}(u,v) and u,v\notin S . We further say that S is a strong \{u,v\} -critical set if vertices from S are adjacent to none of u and v . If S is (strong) \{x,y\} -critical for some vertices x and y we simply say that S is a (strong) critical set. Using these concepts we can characterize graphs in which every independent set is a MV set in the following way. Theorem 5.1 For a graph G , the following statements are equivalent. (i) Every independent set of G is a MV set. (ii) G contains no independent, strong critical set. Proof. Assume first that every independent set of G is a MV set. Suppose for a contradiction that S is an independent, strong \{u,v\} -critical for some vertices u,v\in V(G) . Since S is an independent and strong critical set, S^{\prime}=S\cup\{u,v\} is also independent. Hence by (i), S^{\prime} is a MV set. But since S is \{u,v\} -critical, the vertices u and v are not S^{\prime} -visible, a contradiction. Assume second that G contains no independent, strong critical set. Consider an arbitrary independent set S of G . Let u and v be two vertices of S . Suppose for a contradiction that u,v\in S are not S -visible. Set T=\left(S\cap I_{G}[u,v]\right)\setminus\{u,v\} . Since u and v are not S -visible, T blocks all shortest u,v -paths, that is, T is \{u,v\} -critical. In addition, since S is independent, T is a strong \{u,v\} -critical set. This contradiction completes the argument. \square Setting I_{k}[u,v]=\{w\in I_{G}[u,v]:\ d_{G}(u,w)=k\} , where 0\leq k\leq d_{G}(u,v) , we have the following consequence of Theorem 5.1 . Corollary 5.2 For a graph G with \diam(G)=4 , the following statements are equivalent. (i) Every independent set of G is a MV set. (ii) If d_{G}(u,v)=4 , then G[I_{2}[u,v]] contains an edge. Proof. Since \diam(G)=4 , we infer that the condition (ii) of Theorem 5.1 and the condition (ii) of Corollary 5.2 are equivalent. \square Corollary 5.2 does not extend (at least in a straightforward way) to graphs with diameter at least five. To see it, consider the sporadic example drawn in Fig. 3 . Its diameter is five, the four black vertices form an independent set S , but the vertices x and y are not S -visible. x y Figure 3: An independent set of a diameter five graph which is not a MV set Using the strong product, we can construct graphs of arbitrarily large diameter in which every independent set is a (total) MV set. Proposition 5.3 If n\geq 2 and G is a graph, then every independent set of G\boxtimes K_{n} is a total MV set. Proof. Let S be an independent set of G\boxtimes K_{n} and let x,y\in V(G) . Let P be an arbitrary shortest x,y -path. Assume that P contains an inner vertex (g,i)\in S . If i^{\prime}\in V(K_{n}) , i^{\prime}\neq i , then (g,i^{\prime})\notin S . In P , we can replace (g,i) with (g,i^{\prime}) to get another shortest x,y -path. Continuing this process as long as necessary we arrive at a shortest x,y -path which contains no inner vertices of S . \square 6 Algorithmic time complexity of related problems The independent mutual-visibility number of a graph G was defined in [ 9 ] as the maximum cardinality of a MV set of G that is also independent. Here we refer to it as independent MV number and denote it by \mui(G) . The independent total, dual, and outer MV numbers are defined analogously and denoted by \muti(G) , \mudi(G) , and \muoi(G) , respectively. By definition, 0\leq\sigma^{\mbox{i}}(G)\leq\min\{\alpha(G),\sigma(G)\} (1) holds for every \sigma\in\{\mu,\mut,\mud,\muo\} and graph G . It also follows by the definitions that \muti(G)\leq\mudi(G)\leq\mui(G)\quad\mbox{and}\quad\muti(G)\leq\muoi(G)\leq\mui(G). (2) Theorem 6.1 For each parameter \sigma\in\{\mui,\muti,\mudi,\muoi\} , the following statements hold. (i) For every fixed d\geq 4 , it is NP-complete to decide whether \sigma(G)\geq k holds over the class of graphs of diameter d , where the integer k is a part of the input. (ii) For every fixed d\geq 4 , it is NP-hard to decide whether \sigma(G)=\alpha(G) holds over the class of graphs of diameter d . Further, the NP-completeness of the problem in (i) and the NP-hardness of the problem in (ii) remain true for graphs of diameter three when \sigma\in\{\muti,\mudi,\muoi\} . Proof. To prove (i) and (ii), we use the same polynomial-time reduction from the 3-SAT problem. Let F=C_{1}\wedge\cdots\wedge C_{\ell} be an instance of the 3-SAT problem over the n variables x_{1},\dots,x_{n} . Hence, for every j\in[\ell] , the clause C_{j} is the disjunction of three literals over \{x_{1},\dots,x_{n}\} . It can be assumed that every positive and negative literal is present in some clause. We construct a graph G_{d}(F) of diameter d for every d\geq 4 , and prove that, for each \sigma\in\{\mui,\muti,\mudi,\muoi\} , the relations \sigma(G_{d}(F))\geq n+\ell+d-3 and \sigma(G_{d}(F))=\alpha(G_{d}(F)) hold if and only if F is satisfiable. x_{1}^{+} x_{1}^{-} x_{2}^{+} x_{2}^{-} x_{3}^{+} x_{3}^{-} x_{4}^{+} x_{4}^{-} v_{1} v_{2} v_{3} z_{1} z_{2} c_{1} c_{2} c_{3} c_{1}^{\prime} c_{2}^{\prime} c_{3}^{\prime} Figure 4: Graph G_{5}(F) for F=(x_{1}\lor x_{2}\lor\overline{x}_{3})\land(\overline{x}_{1}\lor\overline{x}_{2}\lor x_{4})\land(x_{2}\lor x_{3}\lor\overline{x}_{4}) . Black vertices form an independent total MV set of cardinality \alpha(G_{5}(F)) . Construction of G_{d}(F) . Define first X=\{x_{1}^{+},x_{1}^{-},\dots,x_{n}^{+},x_{n}^{-}\} , where the elements of X are vertices in G_{d}(F) representing the positive and negative literals over \{x_{1},\dots,x_{n}\} in a natural way. Let C=\{c_{1},\dots,c_{\ell}\} be the set of clause vertices and C^{\prime}=\{c_{1}^{\prime},\dots,c_{\ell}^{\prime}\} be the set of leaves attached to the clause vertices. We further define the vertex set Z=\{v_{1},\dots,v_{d-2}\}\cup\{z_{1},\dots,z_{d-3}\} . To obtain G_{d}(F) , we set X\cup C\cup C^{\prime}\cup Z as its vertex set, and add the edges x_{i}^{+}x_{i}^{-} , x_{i}^{+}v_{1} , x_{i}^{-}v_{1} for every i\in[n] , the edges c_{j}c_{j}^{\prime} for every j\in[\ell] . Further, we make C a complete graph and insert the edges v_{s}v_{s+1} , v_{s}z_{s} , and v_{s+1}z_{s} into Z for every s\in[d-3] . Observe that the order of G_{d}(F) is 1+2(d-3)+2n+2\ell and \diam(G_{d}(F))=d . For an illustration, see Fig. 4 . Claim 1 It holds that \alpha(G_{d}(F))=n+\ell+d-3 . Further, if S is a maximum independent set in G_{d}(F) , then |S\cap Z|=d-3 , |S\cap X|=n , and either S\cap C=\emptyset and S\cap C^{\prime}=C^{\prime} , or S\cap C=\{c_{q}\} and S\cap C^{\prime}=C^{\prime}\setminus\{c_{q}^{\prime}\} for an index q\in[\ell] . Proof. Let S be an independent set in G_{d}(F) . Since Z can be covered by d-3 triangles, |S\cap Z|\leq d-3 . Each of X and C\cup C^{\prime} admits a perfect matching and therefore, |S\cap X|\leq n and |S\cap(C\cup C^{\prime})|\leq\ell . This implies \alpha(G_{d}(F))\leq n+\ell+d-3 . Since S=\{z_{1},\dots,z_{d-3},x_{1}^{+},\dots,x_{n}^{+},c_{1}^{\prime},\dots,c_{\ell}^{\prime}\} is an independent set of cardinality n+\ell+d-3 , the equality follows. We further recall that C induces a complete graph and hence |S\cap C|\leq 1 holds for any independent set S . ( \Box ) Note that Claim 1 and the upper bound in ( 1 ) imply that the relations \sigma(G_{d}(F))\geq n+\ell+d-3 , \sigma(G_{d}(F))=n+\ell+d-3 , and \sigma(G_{d}(F))=\alpha(G_{d}(F)) are equivalent for every \sigma\in\{\mui,\muti,\mudi,\muoi\} . Claim 2 If F is satisfiable, then \sigma(G_{d}(F))=n+\ell+d-3 for each \sigma\in\{\mui,\muti,\mudi,\muoi\} . Proof. Let \phi\colon\{x_{1},\dots,x_{n}\}\rightarrow\{\mbox{true, false}\} a truth assignment that satisfies F and define S^{\prime}=\{z_{1},\dots,z_{d-3},c_{1}^{\prime},\dots,c_{\ell}^{\prime}\}\cup\{x_{i}^{+}\colon\phi(x_{i})=\mbox{false}\}\cup\{x_{i}^{-}\colon\phi(x_{i})=\mbox{true}\}. We first prove that S^{\prime} is an independent total MV set. It is straightforward to check that S^{\prime} is an independent set of cardinality n+\ell+d-3 . To see that it is a total MV set, by Theorem 2.2 , it suffices to show that any two vertices at a distance of two apart are S^{\prime} -visible. Recalling that any two nonadjacent vertices from X can see each other via v_{1} , the S^{\prime} -visibility is easy to check inside Z\cup X . As for C\cup C^{\prime} , if two vertices from C\cup C^{\prime} are at a distance of two, then one of them is a vertex c_{j} from C , and the other is a vertex c_{p}^{\prime} from C^{\prime} such that j\neq p . In this case, the vertices are S^{\prime} -visible via c_{p} . What remains to check is the case of two vertices u\in Z\cup X and w\in C\cup C^{\prime} with d(u,w)=2 . If u\in X and w\in C\cup C^{\prime} , they can always see each other via a vertex from C . If u\in Z and w\in C , then u=v_{1} and w=c_{j} for an integer j\in[\ell] . Since the clause C_{j} is satisfied by a literal x_{i} or \overline{x_{i}} , the corresponding literal vertex, namely x_{i}^{+} or x_{i}^{-} , does not belong to S^{\prime} , and it therefore ensures the S^{\prime} -visibility of v_{1} and c_{j} . Consequently, S^{\prime} is an independent total MV set and \muti(G_{d}(F))=n+\ell+d-3=\alpha(G_{d}(F)) . Then, by definition, S^{\prime} is also an MV set, a dual MV set, and an outer MV set. Thus Claim 2 also holds for \sigma\in\{\mui,\mudi,\muoi\} . ( \Box ) Claim 3 For each invariant \sigma\in\{\mui,\muti,\mudi,\muoi\} , the equality \sigma(G_{d}(F))=n+\ell+d-3 implies that F is satisfiable. Proof. Let S^{\prime\prime} be an independent MV set of cardinality n+\ell+d-3 in G_{d}(F) . Claim 1 then implies |S^{\prime\prime}\cap Z|=d-3 , |S^{\prime\prime}\cap X|=n , and |S^{\prime\prime}\cap(C\cup C^{\prime})|=\ell. Consequently, S^{\prime\prime} contains exactly one vertex from each pair \{x_{i}^{+},x_{i}^{-}\} , and v_{1}\notin S^{\prime\prime} . We may assume, without loss of generality, that S^{\prime\prime}\cap Z=\{z_{1},\dots,z_{d-3}\} . Consider the truth assignment \phi(x_{i})=\left\{\begin{array}[]{ll}\mbox{true};&x_{i}^{-}\in S^{\prime\prime},\\ \mbox{false};&x_{i}^{+}\in S^{\prime\prime}.\end{array}\right. (3) Assume first that S^{\prime\prime}\cap C^{\prime}=C^{\prime} . For each j\in[\ell] , the S^{\prime\prime} -visibility of z_{1}\in S^{\prime\prime} and c_{j}^{\prime}\in S^{\prime\prime} implies that there exists a path z_{1}v_{1}uc_{j}c_{j}^{\prime} such that u\notin S^{\prime\prime} . If u=x_{i}^{+} for an index i\in[n] , then the clause C_{j} in F contains the literal x_{i} and, according to ( 3 ), the clause C_{j} is satisfied. The argument is analogous for u=x_{i}^{-} . It implies the satisfiability of F . In the second case, S\cap C=\{c_{q}\} and S\cap C^{\prime}=C^{\prime}\setminus\{c_{q}^{\prime}\} for an index q\in[\ell] . As for the first case, if c_{j}^{\prime}\in S^{\prime\prime} , then the clause C_{j} is satisfied by the truth assignment in ( 3 ). For the vertex c_{q} , as S^{\prime\prime} is an independent set, no neighbor of c_{q} belongs to S^{\prime\prime} and the clause C_{j} is satisfied by \phi . Again, it shows that F is satisfiable. If \sigma\in\{\muti,\mudi,\muoi\} , then \sigma(G_{d}(F))=n+\ell+d-3 implies \mui(G_{d}(F))=n+\ell+d-3 , and the satisfiability of F follows from the proof above. ( \Box ) From a 3-SAT instance F , the graph G_{d}(F) can be obtained in polynomial time for every d\geq 4 . Let \sigma\in\{\mui,\mudi,\muoi,\muti\} . Claims 1 , 2 , and 3 (together with ( 1 ) and ( 2 )) show that each of \sigma(G_{d}(F))\geq n+\ell+d-3 and \sigma(G_{d}(F))=\alpha(G_{d}(F)) holds if and only if F is satisfiable. Therefore, the 3-SAT problem can be reduced to both decision problems of whether \sigma(G)\geq k and \sigma(G)=\alpha(G) hold for a graph of diameter d for each fixed integer d\geq 4 . This proves the NP-hardness of the decision problems in (i) and (ii). Finally, we note that while the problems in (i) clearly belong to NP, we cannot state the same for the problems in (ii). This finishes the proof for (i) and (ii). Graphs of diameter three. For an instance F of the 3-SAT problem, we obtain the graph G_{3}(F) by deleting z_{1} and v_{2} from G_{4}(F) . Then \diam(G_{3}(F))=3 and \alpha(G_{3}(F))=n+\ell . Assuming that F is satisfiable, we can construct the set S^{\prime} as in the proof of Claim 2 and prove that S^{\prime} is an independent total (and consequently dual and outer) MV set of cardinality n+\ell . For the other direction, we assume that there is an independent outer/dual/total MV set S^{\prime\prime} of cardinality n+\ell in G_{3}(F) . For the outer and total mutual-visibility, we consider the visibility of v_{1} and the leaves c_{j}^{\prime}\in S^{\prime\prime} , for j\in[\ell] , to conclude that every clause is satisfied by the truth assignment given in ( 3 ); while for the dual mutual-visibility we have the same conclusion by considering v_{1} and the clause vertices c_{j} . This proves that the problems in (i) and (ii) remain NP-hard for graphs of diameter three when \sigma\in\{\muti,\mudi,\muoi\} . \square It is known [ 9 , Lemma 2.1] that \diam(G)\leq 3 implies \mui(G)=\alpha(G) . Therefore, the NP-hardness of the decision problem in Theorem 6.1 (ii) cannot be extended to graphs of diameter three if the invariant \mui(G) is considered. On the other hand, it is known by a simple construction [ 17 ] that the decision problem of \alpha(G)\geq k remains NP-complete over the class of graphs of diameter two and three. We may then conclude the following result. Proposition 6.2 For d\in\{2,3\} , it is NP-complete to decide whether \mui(G)\geq k holds over the class of graphs of diameter d , where k is part of the input. 7 Open problems Proposition 3.2 gives a partial solution to the following problem. Problem 1 Characterize the graphs in which every independent set is an outer MV set. Comparing Theorems 4.1 and 4.2 we can derive that the following statements are equivalent for every connected graph G . (i) For every X\subseteq V(G) , the set X is a total MV set of G if and only if X is independent. (ii) G is a dense diamond graph and every edge of G is the middle edge of a convex diamond. We were unable to find any graph that satisfies (ii) above, hence we pose the following: Problem 2 Does there exist a dense diamond graph such that every edge of G is the middle edge of a convex diamond? Related to mutual-visibility and independence, we pose: Problem 3 Characterize the graphs G and H for which every independent set of G\boxtimes H is a MV set.