Recognizing well-dominated graphs is coNP-complete

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

zbMATH Keywords

computational complexityrecognitioncoNP-completewell-dominatedwell-totally-dominated

Mathematics Subject Classification ID

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