354 KB40 KB200820252021Bahadir, SelimEkim, TinazGozüpek, Didemštevilka:2letnik:20str. 209-222DOI:10.26493/1855-3974.2465.571ISSN:1855-3966COBISSID_HOST:92012803URN:URN:NBN:SI:doc-K22UEJKLenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaminimal total dominating setminimalna totalno dominirajoča množicapopolno dominirani grafitotal dominationtotalna dominacijawell-totally-dominated graphsWell-totally-dominated graphs|A subset of vertices in a graph is called a total dominating set if every vertex of the graph is adjacent to at least one vertex of this set. A total dominating set is called minimal if it does not properly contain another total dominating set. In this paper, we study graphs whose all minimal total dominating sets have the same size, referred to as well-totally-dominated (WTD) graphs. We first show that WTD graphs with bounded total domination number can be recognized in polynomial time. Then we focus on WTD graphs with total domination number two. In this case, we characterize triangle-free WTD graphs and WTD graphs with packing number two, and we show that there are only finitely many planar WTD graphs with minimum degree at least three. Lastly, we show that if the minimum degree is at least three then the girth of a WTD graph is at most 12. We conclude with several open questionsPodmnož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šanjiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije