On the Visibility Polynomial of Graphs

2025/07/02 by B, Tonny K, M, Shikhi · 3 citations
#05C31 #05C39 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2507.01851

Abstract

Let G(V,E) be a simple graph and let X subset of V. Two vertices u and v are said to be X-visible if there exists a shortest u,v-path P such that V(P) intersection X is a subset of u, v. A set X is called a mutual-visibility set of G if every pair of vertices in X are X-visible. The visibility polynomial of a graph G is defined as nu (G)=sum_{i >= 0} r_i xⁱ, where r_i denotes the number of mutual-visibility sets in G of cardinality i. In the present paper, the visibility polynomial is studied for some well-known classes of graphs. In particular, the instance at which the number of maximal mutual-visibility sets is equal for cycle graphs is identified. The visibility polynomial of the join of two graphs is studied. The algorithm for computing the visibility polynomial of a graph has been identified to have a time complexity of O(n³.2ⁿ) making the problem computationally intensive for larger graphs.

Citations

• Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets
• Variety of mutual-visibility problems in hypercubes
• Mutual-visibility problems in Kneser and Johnson graphs
• Visibility in Hypercubes
• General position polynomials
• Mutual-visibility problems on graphs of diameter two
• Mutual-visibility sets in Cartesian products of paths and cycles
• Mutual visibility in hypercube-like graphs
• Time-optimal geodesic mutual visibility of robots on grids within minimum area
• Total mutual-visibility in Hamming graphs
• Lower (total) mutual visibility in graphs
• Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products
• Graphs with total mutual-visibility number zero and total mutual-visibility in Cartesian products
• The Mutual Visibility Problem for Fat Robots with Lights
• On the mutual visibility in Cartesian products and triangle-free graphs
• Mutual Visibility in Graphs
• Mutual Visibility by Luminous Robots Without Collisions

Cited by

• On the Mutual Visibility of Some Moore Graphs
• Visibility Polynomial of Some Graph Classes
• Visibility polynomial of corona of two graphs

Related

• Visibility Polynomial of Some Graph Classes
• Mutual Visibility in Graphs
• Variety of mutual-visibility problems in graphs
• Visibility polynomials, dual visibility spectrum, and characterization of total mutual-visibility sets
• Visibility in graphs under edge and vertex removal