2023/07/20 by Serafino Cicerone, Cicerone, Serafino, Gabriele Di Stefano +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #G.2.2 #Graph Labeling and Dimension Problems #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2307.10661
openalex publication_date 2023/07/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The concept of mutual-visibility in graphs has been recently introduced. If X is a subset of vertices of a graph G, then vertices u and v are X-visible if there exists a shortest u,v-path P such that V(P)∩ X ⊆ \u, v\. If every two vertices from X are X-visible, then X is a mutual-visibility set. The mutual-visibility number of G is the cardinality of a largest mutual-visibility set of G. It is known that computing the mutual-visibility number of a graph is NP-complete, whereas it has been shown that there are exact formulas for special graph classes like paths, cycles, blocks, cographs, and grids. In this paper, we study the mutual-visibility in distance-hereditary graphs and show that the mutual-visibility number can be computed in linear time for this class.