20.500.12556/RUP-22688 Mobile mutual-visibility sets in graphs Mobilne množice medsebojne vidnosti v grafih Given a connected graph G, the mutual-visibility number of G is the cardinality of a largest set S such that for every pair of vertices x, y ∈ S there exists a shortest x, y-path whose interior vertices are not contained in S. Assume that a robot is assigned to each vertex of the set S. At each stage, one robot can move to a neighbouring vertex. Then S is a mobile mutual-visibility set of G if there exists a sequence of moves of the robots such that all the vertices of G are visited while maintaining the mutual-visibility property at all times. The mobile mutual-visibility number of G, denoted Mobµ(G), is the cardinality of a largest mobile mutual-visibility set of G. In this paper we introduce the concept of the mobile mutual-visibility number of a graph. We begin with some basic properties of the mobile mutual-visibility number of G and its relationship with the mutual-visibility number of G. We give exact values of Mobµ(G) for particular classes of graphs, i.e. cycles, wheels, complete bipartite graphs, and block graphs (in particular trees). Moreover, we present bounds for the lexicographic product of two graphs and show characterizations of the graphs achieving the limit values of some of these bounds. As a consequence of this study, we deduce that the decision problem concerning finding the mobile mutual-visibility number is NP-hard. Finally, we focus our attention on the mobile mutual-visibility number of line graphs of complete graphs, prism graphs and strong grids of two paths. Naj bo G povezan graf. Število medsebojne vidnosti grafa G je moč največje množice S takšne, da za vsak par vozlišč x, y ∈ S obstaja najkrajša x, y-pot, katere notranja vozlišca niso vsebovana v S. Predpostavimo, da je vsakemu vozlišču iz množice S dodeljen robot. V vsakem koraku se lahko en robot premakne v sosednje vozlišče. Množica S je mobilna množica medsebojne vidnosti grafa G, če obstaja zaporedje premikov robotov, s katerim se obiskujejo vsa vozlišča grafa G, pri čemer se lastnost medsebojne vidnosti ves čas ohranja. Mobilno število medsebojne vidnosti grafa G, označeno z Mobµ(G), je moč največje mobilne množice medsebojne vidnosti grafa G. V tem članku uvedemo pojem mobilnega števila medsebojne vidnosti grafa. Začnemo z nekaterimi osnovnimi lastnostmi mobilnega števila medsebojne vidnosti grafa G in z njegovim razmerjem do števila medsebojne vidnosti grafa G. Podamo natančne vrednosti Mobµ(G) za posebne razrede grafov, torej za cikle, kolesa, popolne bipartitne grafe in bloke (zlasti drevesa). Poleg tega predstavimo meje za leksikografski produkt dveh grafov ter pokažemo karakterizacije grafov, ki dosegajo mejne vrednosti nekaterih teh omejitev. Kot posledico te študije zaključimo, da je odločilni problem iskanja mobilnega števila medsebojne vidnosti NP-težak. Nazadnje svojo pozornost usmerimo na mobilno število medsebojne vidnosti povezavnih grafov polnih grafov, prizem ter močnih mrež dveh poti. mobile mutual-visibility set mutual-visibility number total mutual-visibility mobilna množica medsebojne vidnosti število medsebojne vidnosti popolna medsebojna vidnost true false true Založba Univerze na Primorskem Angleški jezik Slovenski jezik Članek v reviji 2026-03-03 11:31:45 2026-03-03 11:31:45 2026-03-04 03:09:10 0000-00-00 00:00:00 2026 0 0 21 str. no. 1, [article no.] P1.10 Vol. 26 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-12-18 51 1855-3974 10.26493/1855-3974.3410.9bc AMC_Dettlaff,_Lemańska,_Rodriguez-Velazquez,_G._Yero_2026.pdf AMC_Dettlaff,_Lemańska,_Rodriguez-Velazquez,_G._Yero_2026.pdf 1 A24E12A12BD5890262614431BFA2F7D3 e0b667d4fa6613d74631c9d8ef6ced28636fcc74cce604c92d64107ee67e4f64 032aad41-16ed-11f1-b092-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=33037 Založba Univerze na Primorskem 0 0 0