RT journal article
T1 Variety of mutual-visibility problems in graphs
A1 Cicerone, Serafino
A1 Di Stefano, Gabriele
A1 Drožđek, Lara
A1 Hedžet, Jaka
A1 Klavžar, Sandi
A1 González Yero, Ismael
A2 Matemáticas
K1 Computational complexity
K1 Dual mutual-visibility number
K1 Grid graph
K1 Mutual-visibility
K1 Outer mutual-visibility
K1 Torus graph
K1 Total mutual-visibility
AB 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 each 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 and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be X-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.
PB Elsevier
SN 0304-3975
YR 2023
FD 2023
LK http://hdl.handle.net/10498/32540
UL http://hdl.handle.net/10498/32540
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 05-nov-2026