论文标题
良好的主导图
Well-Totally-Dominated Graphs
论文作者
论文摘要
如果图形的每个顶点与该集合的至少一个顶点相邻，则图中的顶点子集称为总统治集。如果完全不正确包含另一个总统治集，则总占主导地位称为最小值。在本文中，我们研究了所有最小总占主导地位的图形，其大小相同，所提到的良好主导（WTD）图。我们首先表明，具有界限总统治数的WTD图可以在多项式时间内识别。然后，我们专注于全部统治第二的WTD图。在这种情况下，我们表征了带有第二号包装的无三角形WTD图和WTD图，并且我们表明只有许多具有最低度至少三个的平面WTD图有限。最后，我们表明，如果最小程度至少为三个，那么WTD图的周长最多为12。
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.
