The vertex visibility number of graphs

If x ∈ V ( G ), then S ⊆ V ( G )∖{ x } is an x -visibility set if for each y ∈ S there exists a shortest x, y -path avoiding S . The x -visibility number v x ( G ) is the maximum cardinality of an x -visibility set, and the maximum value of v x ( G ) between all vertices x of G is the vertex visibility number vv( G ) of G . It is proved that vv( G ) is equal to the largest possible number of leaves of a shortest-path tree of G . Deciding whether v x ( G ) ≥ k holds for given G , a vertex x ∈ V ( G ), and a positive integer k is NP-complete even for graphs of diameter 2. Several general sharp lower and upper bounds on the vertex visibility number are proved. The vertex visibility number of Cartesian products is also bounded from below and above, and the exact value of the vertex visibility number is determined for square grids, square prisms, and square toruses.