Well-totally-dominated graphs

DOI10.26493/1855-3974.2465.571MaRDI QIDQ3390049zbMATH OpenOpenAlexFDO

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

Publication date 24 March 2022

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2010.02341

zbMATH Keywords

total dominating setwell-totally-dominated graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 4063149
• scientific article; zbMATH DE number 1109413
• On total dominating sets in graphs
• Well-dominated graphs without cycles of lengths 4 and 5
• Total domination in plane triangulations

Cites work

• A revision and extension of results on 4-regular, 4-connected, claw-free graphs
• Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
• Dual subimplicants of positive Boolean functions
• scientific article; zbMATH DE number 5902609 (Why is no real title available?)
• scientific article; zbMATH DE number 4202288 (Why is no real title available?)
• scientific article; zbMATH DE number 3910441 (Why is no real title available?)
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• scientific article; zbMATH DE number 1286748 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1161341 (Why is no real title available?)
• scientific article; zbMATH DE number 1529462 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• On a class of graphs with large total domination number
• On the computational complexity of upper total domination
• Total domination in graphs
• Total domination in graphs
• Triangulations and equality in the domination chain
• WELL-COVERED GRAPHS: A SURVEY
• Well-dominated graphs without cycles of lengths 4 and 5

Cited in

(7)

• On graphs all of whose total dominating sequences have the same length
• Well-dominated graphs without cycles of lengths 4 and 5
• scientific article; zbMATH DE number 4063149 (Why is no real title available?)
• scientific article; zbMATH DE number 1161341 (Why is no real title available?)
• Well-indumatched Trees and Graphs of Bounded Girth
• Recognizing well-dominated graphs is coNP-complete
• Well paired-dominated graphs

This page was built for publication: Well-totally-dominated graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3390049)