413 KB35 KB200820252021Klavžar, SandiRall, Douglas F.Yero, Ismael G.številka:1letnik:21str. 33-44DOI:10.26493/1855-3974.2384.77dISSN:1855-3966COBISSID:72019203URN:URN:NBN:SI:doc-4TTZIGJHenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneadisociacijske množicegrafikrepki solventni grafmnožiceračunska zahtevnostGeneral d-position sets|The general ?$d$?-position number ?${\rm gp}_d(G)$? of a graph ?$G$? is the cardinality of a largest set ?$S$? for which no three distinct vertices from ?$S$? lie on a common geodesic of length at most ?$d$?. This new graph parameter generalizes the well studied general position number. We first give some results concerning the monotonic behavior of ?${\rm gp}_d(G)$? with respect to the suitable values of ?$d$?. We show that the decision problem concerning finding ?${\rm gp}_d(G)$? is NP-complete for any value of ?$d$?. The value of ?${\rm gp}_d(G)$? when ?$G$? is a path or a cycle is computed and a structural characterization of general ?$d$?-position sets is shown. Moreover, we present some relationships with other topics including strong resolving graphs and dissociation sets. We finish our exposition by proving that ?${\rm gp}_d(G)$? is infinite whenever ?$G$? is an infinite graph and ?$d$? is a finite integerŠtevilo ?$d$?-splošne lege ?${\rm gp}_d(G)$? grafa ?$G$? je kardinalnost največje množice ?$S$?, za katero nobena trojica volišč ne leži na skupni najkrajši poti dolžine kvečjemu ?$d$?. Ta novi grafovski parameter posplošuje dobro preučeno število splošne lege. Najprej podamo nekaj rezultatov v zvezi z monotonim vedenjem ?${\rm gp}_d(G)$? glede na primerne vrednosti ?$d$?. Pokažemo, da je odločitveni problem iskanja ?${\rm gp}_d(G)$? NP-poln za vse ?$d$?. Izračunana je vrednost ?${\rm gp}_d(G)$?, kadar je ?$G$? pot ali cikel, dokazana je tudi strukturna karakterizacija množic v ?$d$?-splošni legi. Poleg tega predstavljamo nekatere odnose z drugimi temami, vključno s krepkimi solventnimi grafi in disociacijskimi množicami. Našo predstavitev zaključimo z dokazom, da je ?${\rm gp}_d(G)$? neskončno, kadar je ?$G$? neskončen graf in ?$d$? končno celo številoTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije