Let G=(V,E) be a graph and P⊆V 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.

Mutual visibility in graphs

Di Stefano G.
2022-01-01

Abstract

Let G=(V,E) be a graph and P⊆V 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/199639
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 19
social impact