General d-position sets - Klavžar, Sandi (Ars mathematica contemporanea, 2021)
Š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 število.
Keywords: disociacijske množice; grafi; krepki solventni graf; množice; računska zahtevnost