Efficiently recognizing graphs with equal independence and annihilation numbers

DOI10.1016/j.ipl.2023.106387arXiv2204.11094MaRDI QIDQ6161447

Dieter Rautenbach, Johannes Rauch

Publication date: 5 June 2023

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.11094

zbMATH Keywords

combinatorial problemsindependence numberannihilation number

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Counterexamples to the characterisation of graphs with equal independence and annihilation number

Cites Work

• Unnamed Item
• Graphs with equal independence and annihilation numbers
• Almost 2-SAT is fixed-parameter tractable
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On Representatives of Subsets
• Reducibility among Combinatorial Problems
• Paths, Trees, and Flowers
• The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number