Well-totally-dominated graphs

Selim Bahadır, Tınaz Ekim, Didem Gözüpek


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


Total domination, well-totally-dominated graphs, minimal total dominating sets

Full Text:


DOI: https://doi.org/10.26493/1855-3974.2465.571

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications