Article Per Year (5 Year)
p-Index From 2021 - 2026
0.23
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Biswajit Deb
Birangana Sati Sadhani Rajyik Vishwavidyalaya, Golaghat, Assam, India, 785621
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
NP-completeness and an ILP formulation for the P3-convex domination problem Anjan Gautam; Biswajit Deb; Pinaki Mitra; Puran Dangal
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 14, No 2 (2026): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2026.14.2.9

Abstract

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.
Co-Authors Anjan Gautam Pinaki Mitra Puran Dangal