Show simple item record

dc.contributor.authorBrešar, B.
dc.contributor.authorGonzález Yero, Ismael 
dc.contributor.otherMatemáticases_ES
dc.date.accessioned2024-03-15T07:27:12Z
dc.date.available2024-03-15T07:27:12Z
dc.date.issued2024
dc.identifier.issn0096-3003
dc.identifier.urihttp://hdl.handle.net/10498/31409
dc.description.abstractGiven 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 these concepts, defined as the smallest possible cardinality among all maximal (total) mutual-visibility sets in G, and denote them by μ−(G) and μ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 μ−(G)−μt−(G) and μt−(G)−μ−(G) can be arbitrarily large. We characterize graphs G with some small values of μ−(G) and μt−(G), and prove a useful tool called the 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 the Bollobá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 μt−(G)es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherElsevieres_ES
dc.rightsAtribución-NoComercial-CompartirIgual 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-sa/4.0/*
dc.sourceApplied Mathematics and Computation - 2024, vol.465es_ES
dc.subjectMutual-visibility setes_ES
dc.subjectMutual-visibility numberes_ES
dc.subjectTotal mutual-visibility setes_ES
dc.subjectComputational complexityes_ES
dc.titleLower (total) mutual-visibility number in graphses_ES
dc.typejournal articlees_ES
dc.rights.accessRightsopen accesses_ES
dc.identifier.doi10.1016/J.AMC.2023.128411
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-105824GB-I00/ES/OPTIMIZACION MATEMATICA Y COMBINATORIA EN REDES/ es_ES
dc.type.hasVersionVoRes_ES


Files in this item

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial-CompartirIgual 4.0 Internacional
This work is under a Creative Commons License Atribución-NoComercial-CompartirIgual 4.0 Internacional