论文标题
识别以良好为主的图是概括的
Recognizing well-dominated graphs is coNP-complete
论文作者
论文摘要
如果每一个最小的顶点盖为$ g $，则图表$ g $的覆盖量最低，而如果每一套最小的$ g $的主要主导套件最低，则图表$ g $是良好的。在[Plummer，JCT 1970]中启动了有关覆盖良好图的研究，首先在[Finbow，Hartnell and Nowakow，AC 1988]中引入了以良好为主导的图。良好的图表覆盖良好，两类在文献中都得到了广泛的研究。 [Chvátal和Slater，AODM 1993]和[Sankaranarayana and Stewart，Networks 1992]证明了对覆盖良好的图的识别，但自介绍以来已经打开了良好的图形的复杂性。我们通过证明识别良好主导的图是局限性完成的，缩小了这一复杂性差距。这解决了一个众所周知的公开问题（C.F. [Levit and Tankus，DM 2017]和[Gözüpek，Hujdurovic和Milanič，DMTCS 2017]），这是在[Caro，Sebő和Tarsi，Jalg，Jalg 1996]中首次提出的。令人惊讶的是，我们的证明非常简单，尽管这是一个长期的开放问题。最后，我们表明，识别以良好为主导的图是概括的，回答了[Bahad \ ir，Ekim和Gözüpek，AMC 2021]的问题。
A graph $G$ is well-covered if every minimal vertex cover of $G$ is minimum, and a graph $G$ is well-dominated if every minimal dominating set of $G$ is minimum. Studies on well-covered graphs were initiated in [Plummer, JCT 1970], and well-dominated graphs were first introduced in [Finbow, Hartnell and Nowakow, AC 1988]. Well-dominated graphs are well-covered, and both classes have been widely studied in the literature. The recognition of well-covered graphs was proved coNP-complete by [Chvátal and Slater, AODM 1993] and by [Sankaranarayana and Stewart, Networks 1992], but the complexity of recognizing well-dominated graphs has been left open since their introduction. We close this complexity gap by proving that recognizing well-dominated graphs is coNP-complete. This solves a well-known open question (c.f. [Levit and Tankus, DM 2017] and [Gözüpek, Hujdurovic and Milanič, DMTCS 2017]), which was first asked in [Caro, Sebő and Tarsi, JAlg 1996]. Surprisingly, our proof is quite simple, although it was a long-standing open problem. Finally, we show that recognizing well-totally-dominated graphs is coNP-complete, answering a question of [Bahad\ir, Ekim, and Gözüpek, AMC 2021].
