Mutual Visibility in Graphs

DOI10.1016/J.AMC.2021.126850zbMATH Open1510.05054arXiv2105.02722MaRDI QIDQ6367006

Gabriele Di Stefano

Publication date: 6 May 2021

Abstract: Let $G=(V,E)$ be a graph and $PsubseteqV$ a set of points. Two points are mutually visible if there is a shortest path between them without further points. $P$ is a mutual-visibility set if its points are pairwise mutually visible. The mutual-visibility number of $G$ is the size of any largest mutual-visibility set. In this paper we start the study about this new invariant and the mutual-visibility sets in undirected graphs. We introduce the mutual-visibility problem which asks to find a mutual-visibility set with a size larger than a given number. We show that this problem is NP-complete, whereas, to check whether a given set of points is a mutual-visibility set is solvable in polynomial time. Then we study mutual-visibility sets and mutual-visibility numbers on special classes of graphs, such as block graphs, trees, grids, tori, complete bipartite graphs, cographs. We also provide some relations of the mutual-visibility number of a graph with other invariants.

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Mutual Visibility in Graphs