20.500.12556/DiRROS-18649 Variety of mutual-visibility problems in graphs 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)\cap X \subseteq \{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. mutual-visibility total mutual-visibility dual mutual-visibility number outer mutual-visibility grid graphs torus graphs computational complexity vzajemna vidnost celotna vzajemna vidnost število dualne vzajemne vidnosti število zunanje vzajemne vidnosti rešetke torusni grafi računska zahtevnost true false true Angleški jezik Slovenski jezik Neznano 2024-04-10 08:46:43 2024-04-10 08:46:43 2024-04-11 03:34:32 0000-00-00 00:00:00 2023 0 0 Soavtorji: Gabriele Di Stefano, Lara Drožđek, Jaka Hedžet, Sandi Klavžar, Ismael G. Yero; Spletna objava: 6. 8. 2023; 13 str. art. no. ǂ114096 Vol. 974 Sep. 2023 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2023-09-01 519.17 0304-3975 10.1016/j.tcs.2023.114096 161787907 1-s2.0-S0304397523004097-main.pdf 1-s2.0-S0304397523004097-main.pdf 1 02946E0363BE3E74B415BF7F23B898C6 88d9faf051d3787991964d8a85bc6d8c7c4a13597d63ce944ec4914371a7a6dd b3ec4534-f6f5-11ee-ae20-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25475 https://www.sciencedirect.com/science/article/pii/S0304397523004097 1 54d04869-f6f5-11ee-ae20-001a4af901a5 https://dirros.openscience.si/Dokument.php?lang=slv&id=25474 Inštitut za matematiko, fiziko in mehaniko 0 0 0