TOPICS
Search

Mutual-Visibility Set


Let G be a simple graph on vertex set V and let X be a subset of V. Two vertices u,v in V are called "X-visible" if there exists a shortest path from u to v such that none of the internal vertices on the path belong to X. A set X is then called a mutual-visibility set of G if every pair of vertices in X is X-visible (Di Stefano 2022, Tonny and Shikhi 2025).

The maximum cardinality of a mutual-visibility set of G is called the mutual-visibility number.

The visibility polynomial records mutual-visibility sets by size: if r_k is the number of mutual-visibility sets of G of size k, and mu=mu(G) is the mutual-visibility number, then

 V(G)=sum_(k=0)^mur_kx^k.

See also

Graph Geodesic, Mutual-Visibility Number, Shortest Path, Visibility Polynomial

Explore with Wolfram|Alpha

References

Di Stefano, G. "Mutual Visibility in Graphs." Appl. Math. Comput. 419, 126850, 2022.Tonny, K. B. and Shikhi, M. "On the Visibility Polynomial of Graphs." 2 Jul 2025. https://arxiv.org/abs/2507.01851.

Cite this as:

Weisstein, Eric W. "Mutual-Visibility Set." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Mutual-VisibilitySet.html

Subject classifications