Well-totally-dominated graphs

angleški

2021

letnik 20, številka 2

minimalna totalno dominirajoča množica   popolno dominirani grafi   totalna dominacija

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Podmnožica vozlišč grafa se imenuje totalno dominirajoča množica, če je vsako vozlišče grafa sosedno najmanj enemu vozlišču te množice. Totalno dominirajoča množica se imenuje minimalna, če ne vsebuje nobene manjše totalne dominirajoče množice. V članku raziskujemo grafe, pri katerih imajo vse njihove minimalne totalno dominirajoče množice isto velikost; takšnim grafom pravimo popolno dominirani grafi. Najprej pokažemo, da lahko popolno dominirane grafe, katerih popolno dominacijsko število je omejeno, prepoznamo v polinomskem času. Nato se osredotočimo na popolno dominirane grafe, katerih popolno dominacijsko število je enako dve. Med takimi grafi karakteriziramo tiste brez trikotnikov ter tiste s pakirnim številom enakim dve; pokažemo tudi, da obstaja samo končno mnogo ravninskih popolno dominiranih grafov, katerih minimalna stopnja je najmanj tri. Nazadnje pokažemo še, da je, kadar je minimalna stopnja najmanj tri, ožina popolno dominiranega grafa največ 12. Članek sklenemo z več odprtimi vprašanji.

22.11.2022