Recognizing well-dominated graphs is coNP-complete
From MaRDI portal
Publication:6072202
DOI10.1016/j.ipl.2023.106419zbMath1529.05122arXiv2208.08864OpenAlexW4379141267MaRDI QIDQ6072202
Akanksha Agrawal, Philipp Kindermann, Henning Fernau, Kevin Mann, Uéverton S. Souza
Publication date: 12 October 2023
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2208.08864
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- It is hard to know when greedy is good for finding independent sets
- Well-covered circulant graphs
- A characterization of well covered graphs of girth 5 or greater
- Well-covered graphs and extendability
- The many facets of upper domination
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Very well covered graphs
- Well irredundant graphs
- Well-covered claw-free graphs
- Graph sandwich problem for the property of being well-covered and partitionable into \(k\) independent sets and \(\ell\) cliques
- Partitions and well-coveredness: the graph sandwich problem
- On the probe problem for \((r, \ell)\)-well-coveredness: algorithms and complexity
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- A revision and extension of results on 4-regular, 4-connected, claw-free graphs
- Recognizing well covered graphs of families with special \(P _{4}\)-components
- Well-dominated graphs without cycles of lengths 4 and 5
- On well-dominated graphs
- On the probe problem for \((r,\ell )\)-well-coveredness
- Well-totally-dominated graphs
- Complexity results for well‐covered graphs
- Properties of Hereditary Hypergraphs and Middle Graphs
- WELL-COVERED GRAPHS: A SURVEY
- A characterization of well‐covered graphs that contain neither 4‐ nor 5‐cycles
- Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs
- Recognizing Greedy Structures
- Well covered simplicial, chordal, and circular arc graphs
- Reducibility among Combinatorial Problems
- Some covering concepts in graphs
This page was built for publication: Recognizing well-dominated graphs is coNP-complete