The vertex visibility number of graphs

2025/10/22 by Dhanya Roy, Gabriele Di Stefano, Roy, Dhanya +5
Computer Science · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2510.19452

openalex publication_date 2025/10/22 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28

Abstract

If x∈ V(G), then S⊆ V(G)∖\x\ is an x-visibility set if for any 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) among all vertices x of G is the vertex visibility number \rm vv(G) of G. It is proved that \rm 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.

Citations

• Varieties of mutual-visibility and general position on Sierpiński graphs
• The General Position Problem: A Survey
• Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets
• Counting largest mutual-visibility and general position sets of glued t-ary trees
• Mutual-visibility and general position sets in Sierpiński triangle graphs
• Coloring the vertices of a graph with mutual-visibility property
• Mutual-visibility and general position in double graphs and in Mycielskians
• Mutual-visibility problems on graphs of diameter two
• Mutual-visibility sets in Cartesian products of paths and cycles
• Lower (total) mutual visibility in graphs
• Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products
• The iteration time and the general position number in graph convexities
• Variety of mutual-visibility problems in graphs
• Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products
• Mutual-visibility in strong products of graphs via total mutual-visibility
• On the Vertex Position Number of Graphs
• On the General Position Number of Mycielskian Graphs
• On the mutual visibility in Cartesian products and triangle-free graphs
• Mutual Visibility in Graphs
• Max-Leaves Spanning Tree is APX-hard for Cubic Graphs

Related

• On the Vertex Position Number of Graphs
• Visibility in graphs under edge and vertex removal
• On the Visibility Polynomial of Graphs
• Variety of mutual-visibility problems in graphs
• Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products