The adjacency dimension of graphs - Bermudo, Sergio (Ars mathematica contemporanea, 2022)
Znano je, da je problem izračunavanja sosednostne dimenzije grafa NP-težaven. Zato je smiselno določiti sosednostno dimenzijo za posebne družine grafov ali pa dobiti dobre meje za to invarianto. V tem članku določimo splošne meje za sosednostno dimenzijo grafa ?$G$?, izražene z znanimi parametri grafa ?$G$?. Preučujemo ostrost teh meja in za določene razrede grafov dobimo sklenjene formule. Pokažemo tudi, da obstajajo tesni odnosi med sosednostno dimenzijo in drugimi parametri, kot so npr. dominacijsko število, lokacijsko-dominacijsko število, 2-dominacijsko število, neodvisno 2-dominacijsko število, točkovno krovno število, neodvisnostno število in super dominacijsko število.
Keywords: adjacency dimension; independence number; location-domination number; lokacijsko-dominacijsko število; metric dimension; metrična dimenzija; neodvisnostno število; sosednostna dimenzija; super dominacijsko število; super domination number