Lower (total) mutual-visibility number in graphs

DOI10.1016/J.AMC.2023.128411arXiv2307.02951OpenAlexW4387924925MaRDI QIDQ6128619

Boštjan Brešar, Ismael G. Yero

Publication date: 16 April 2024

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: Given a graph $G$, a set $X$ of vertices in $G$ satisfying that between every two vertices in $X$ (respectively, in $G$) there is a shortest path whose internal vertices are not in $X$ is a mutual-visibility (respectively, total mutual-visibility) set in $G$. The cardinality of a largest (total) mutual-visibility set in $G$ is known under the name (total) mutual-visibility number, and has been studied in several recent works. In this paper, we propose two lower variants of the mentioned concepts, defined as the smallest possible cardinality among all maximal (total) mutual-visibility sets in $G$, and denote them by $m{u}^{-}(G)$ and $m{u}_t^{-}(G)$, respectively. While the total mutual-visibility number is never larger than the mutual-visibility number in a graph $G$, we prove that both differences $m{u}^{-}(G)-m{u}_t^{-}(G)$ and $m{u}_t^{-}(G)-m{u}^{-}(G)$ can be arbitrarily large. We characterize graphs $G$ with some small values of $m{u}^{-}(G)$ and $m{u}_t^{-}(G)$, and prove a useful tool called Neighborhood Lemma, which enables us to find upper bounds on the lower mutual-visibility number in several classes of graphs. We compare the lower mutual-visibility number with the lower general position number, and find a close relationship with Bollob'{a}s-Wessel theorem when this number is considered in Cartesian products of complete graphs. Finally, we also prove the NP-completeness of the decision problem related to $m{u}_t^{-}(G)$.

Full work available at URL: https://arxiv.org/abs/2307.02951

zbMATH Keywords

computational complexitymutual-visibility numbermutual-visibility settotal mutual-visibility set

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Mutual-visibility problems on graphs of diameter two

This page was built for publication: Lower (total) mutual-visibility number in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6128619)