Mutual d-visibility in Graphs

Abstract Let d be a positive integer. The mutual d -visibility number $${\mu ^d}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>μ</mml:mi> <mml:mi>d</mml:mi> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> of a graph G is introduced as the cardinality of the largest mutual d -visibility set. That is, $$X\subseteq V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is a mutual d -visibility set if for any pair of vertices $$x,y\in X$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>,</mml:mo> <mml:mi>y</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>X</mml:mi> </mml:mrow> </mml:math> , the distance between them is larger than d , or there exists a shortest x , y -path in G whose internal vertices are not in X . Several combinatorial and computational aspects of $${\mu ^d}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>μ</mml:mi> <mml:mi>d</mml:mi> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> are given in this work. Finally, the NP-completeness of the decision problem concerning finding $${\mu ^d}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msup> <mml:mi>μ</mml:mi> <mml:mi>d</mml:mi> </mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> is proved.