Efficient Minus and Signed Domination in Proper Interval Graphs with a Totally Unimodular Structure
Abstract
The efficient minus domination problem (EMDP) and the efficient signed domination problem (ESDP) are domination-type problems in graphs. These problems are known to be NP-complete on chordal graphs and polynomially solvable on chain interval graphs, while the complexity on proper interval graphs remained open. By exploiting the totally unimodular structure of the closed-neighborhood matrix induced by a proper interval ordering, we obtain linear programming formulations under which both the EMDP and ESDP become polynomially solvable. The same perspective naturally extends to vertex-weighted settings and to other domination variants defined by similar neighborhood constraints.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Interconnection Networks and Systems
Publication details
- Journal / source
- Axioms
- Publisher
- MDPI AG
- Volume
- 15
- Issue
- 3
- Pages
- 191–191
- Publication date
- 5 March 2026
- Language
- EN