398 KB64 KB142 KB7 KB2026Dettlaff, MagdaLemańska, MagdalenaRodríguez-Velázquez, Juan AlbertoYero, Ismael G.številka:1, article p1.10letnik:26str. 1-21DOI:10.26493/1855-3974.3410.9bcISSN:1855-3974COBISSID_HOST:288697859URN:URN:NBN:SI:doc-P20BGLTJenUniverza na PrimorskemArs mathematica contemporaneamobile mutual-visibility setmobilna množica medsebojne vidnostimutual-visibility numberpopolna medsebojna vidnostštevilo medsebojne vidnostitotal mutual-visibilityMobile mutual-visibility sets in graphs|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 pathsNaj 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 potiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije