Š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.

Pravice

URN

URN:NBN:SI:DOC-4TTZIGJH

COBISSID

72019203

DOI

10.26493/1855-3974.2384.77d

Objavljeno

22.11.2022

Metapodatki

Citiranje

APA:

Klavžar, Sandi, Rall, Douglas F., Yero, Ismael G. (2021). General d-position sets. Ars mathematica contemporanea, letnik 21, številka 1, str. 33-44. URN:NBN:SI:DOC-4TTZIGJH from http://www.dlib.si

MLA:

Klavžar, Sandi, Rall, Douglas F., Yero, Ismael G.. "General d-position sets." Ars mathematica contemporanea letnik 21. številka 1 (2021) str. 33-44.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-4TTZIGJH>

Ars mathematica contemporanea
2008-
(Zbirni zapis)