Mutual d-visibility in Graphs

Abstract

Let d be a positive integer. The mutual d-visibility number μd(G) of a graph G is introduced as the cardinality of the largest mutual d-visibility set. That is, X⊆V(G) is a mutual d-visibility set if for any pair of vertices x,y∈X, 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 μd(G) are given in this work. Finally, the NP-completeness of the decision problem concerning finding μd(G) is proved.