Mutual k-Visibility in Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911480904941568 |
|---|---|
| author | B, Tonny K M, Shikhi |
| author_facet | B, Tonny K M, Shikhi |
| contents | 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 $μ_k(G)$ of a graph $G$ and establish its basic properties, including monotonicity and stabilization for sufficiently large values of $k$. Some bounds on $μ_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 $μ_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\bigl(|S|(|V(G)|+|E(G)|)+|S|^2\bigr)$. In addition, we introduce strengthened variants-total, outer, and dual mutual $k$-visibility. We also define the mutual $k$-visibility covering number $τ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14500 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Mutual k-Visibility in Graphs B, Tonny K M, Shikhi Combinatorics 05C12, 05C69, 05C85 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 $μ_k(G)$ of a graph $G$ and establish its basic properties, including monotonicity and stabilization for sufficiently large values of $k$. Some bounds on $μ_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 $μ_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\bigl(|S|(|V(G)|+|E(G)|)+|S|^2\bigr)$. In addition, we introduce strengthened variants-total, outer, and dual mutual $k$-visibility. We also define the mutual $k$-visibility covering number $τ_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. |
| title | Mutual k-Visibility in Graphs |
| topic | Combinatorics 05C12, 05C69, 05C85 |
| url | https://arxiv.org/abs/2602.14500 |