Mutual k-Visibility in Graphs

Mutual visibility in graphs requires pairs of vertices to be connected by shortest paths that avoid all other vertices of a prescribed set, a condition that is often overly restrictive. In this paper, we introduce a new variant, called mutual $k$-visibility, which permits at most $k$ internal vertices of the set to lie on a shortest path. This parameterized approach naturally generalizes classical mutual visibility and provides a graded notion of obstruction tolerance. We define the mutual $k$-visibility number ${\mu }_k(G)$ of a graph $G$ and establish its basic properties, including monotonicity and stabilization for sufficiently large values of $k$. Some bounds on ${\mu }_k(G)$ are obtained in terms of diameter, maximum degree, and girth. We further analyze $(X,k)$-visibility in convex graphs and determine exact values of ${\mu }_k(G)$ for some fundamental graph classes. In addition, for block graphs, we introduce the notion of $k$-admissible sets in the associated block–cutpoint tree and show how these sets characterize mutual $k$-visibility in the original graph. Moreover, we present a polynomial-time algorithm, MkV, that decides whether a given subset $S\subseteq V(G)$ forms a mutual $k$-visibility set in $G$. The algorithm has time complexity $O(\mathrm{\mid }S\mathrm{\mid }(\mathrm{\mid }V(G)\mathrm{\mid }+\mathrm{\mid }E(G)\mathrm{\mid })+\mathrm{\mid }S{\mathrm{\mid }}^2)$. In addition, we introduce strengthened variants-total, outer, and dual mutual $k$-visibility. We also define the mutual $k$-visibility covering number ${\tau }_k(G)$, the minimum number of mutual $k$-visible sets required to partition $V(G)$, thereby extending the theory from extremal subsets to structural decompositions.