NP-completeness and an ILP formulation for the P3-convex domination problem

Anjan Gautam (Department of Mathematics, Sikkim Manipal Institute of technology, Sikkim Manipal University,)
Biswajit Deb (Birangana Sati Sadhani Rajyik Vishwavidyalaya, Golaghat, Assam, India, 785621)
Pinaki Mitra (Indian Institute of Technology Guwahati)
Puran Dangal (Department of Mathematics, Sikkim Manipal Institute of technology, Sikkim Manipal University,)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 14, No 2 (2026): Electronic Journal of Graph Theory and Applications

A set S ⊆ V(G) of a graph G is called a P3-convex dominating set if it is a dominating set and for every path u − w − v of length two with u, v ∈ S, the vertex w belongs to S. The P3-convex domination number γ3c(G) is the cardinality of a minimum P3-convex dominating set (P3-CDS). In this paper, we present several foundational results concerning this parameter. First, we show that for any integers n ≥ 6 and 1 ≤ k ≤ n, there exists a graph G of order n such that γ3c(G) = k. We then show that the P3-CONVEX DOMINATING SET decision problem is NP-complete, even when restricted to bipartite graphs. Finally, we present an integer linear programming formulation for the P3-convex dominating set problem and prove that its optimal solutions correspond exactly to minimum P3-convex dominating sets.