Recognizing well-dominated graphs is coNP-complete
From MaRDI portal
Abstract: A graph is well-covered if every minimal vertex cover of is minimum, and a graph is well-dominated if every minimal dominating set of 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'atal 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"{o}z"{u}pek, Hujdurovic and Milaniv{c}, DMTCS 2017]), which was first asked in [Caro, SebH{o} 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 [Bahadir, Ekim, and G"oz"upek, AMC 2021].
Recommendations
Cites work
- A characterization of well covered graphs of girth 5 or greater
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- 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
- Complexity results for well‐covered graphs
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- FPT algorithms to recognize well covered graphs
- Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
- scientific article; zbMATH DE number 434906 (Why is no real title available?)
- scientific article; zbMATH DE number 3873377 (Why is no real title available?)
- scientific article; zbMATH DE number 4202288 (Why is no real title available?)
- scientific article; zbMATH DE number 4063149 (Why is no real title available?)
- scientific article; zbMATH DE number 3614795 (Why is no real title available?)
- scientific article; zbMATH DE number 637286 (Why is no real title available?)
- scientific article; zbMATH DE number 1161341 (Why is no real title available?)
- scientific article; zbMATH DE number 205349 (Why is no real title available?)
- It is hard to know when greedy is good for finding independent sets
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
- On the probe problem for (r, )-well-coveredness
- On well-dominated graphs
- Partitions and well-coveredness: the graph sandwich problem
- Properties of Hereditary Hypergraphs and Middle Graphs
- Recognizing Greedy Structures
- Recognizing well covered graphs of families with special \(P _{4}\)-components
- Reducibility among combinatorial problems
- Some covering concepts in graphs
- The many facets of upper domination
- Very well covered graphs
- Well covered simplicial, chordal, and circular arc graphs
- Well irredundant graphs
- Well-covered circulant graphs
- Well-covered claw-free graphs
- Well-covered graphs and extendability
- WELL-COVERED GRAPHS: A SURVEY
- Well-dominated graphs without cycles of lengths 4 and 5
- Well-totally-dominated graphs
This page was built for publication: Recognizing well-dominated graphs is coNP-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6072202)
