NP-completeness and an ILP formulation for the P3-convex domination problem
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.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2026.14.2.9
References
R.T. Aunzo Jr. and E.L. Enriquez, Convex doubly connected domination in graphs, Appl. Math. Sci. 9 (2015), 6723–6734.
R.M. Barbosa, E.M.M. Coelho, M.C. Dourado, D. Rautenbach and J.L. Szwarcfiter, On the Carathéodory number for the convexity of paths of order three, SIAM J. Discrete Math. 26 (2012), 929–939.
C.C. Centeno, M.C. Dourado, L.D. Penso, D. Rautenbach, and J.L. Szwarcfiter, Irreversible conversion of graphs, Theoret. Comput. Sci. 412 (2011), 3693–3700.
M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Math. 206 (1999), 91–95.
M. Chellali, O. Favaron, A. Hansberg, and L. Volkmann, k-domination and k-independence in graphs: A survey, Graphs Combin. 28 (2012), 1–55.
J. Cyman, M. Lemańska, and J. Raczek, Graphs with convex domination number close to their order, Discuss. Math. Graph Theory 26 (2006), 307–316.
J.A. Dayap and E.L. Enriquez, Outer-convex domination in graphs, Discrete Math. Algorithms Appl. 12 (2020), 2050008.
P. Duchet, Convex sets in graphs II. Minimal path convexity, J. Combin. Theory Ser. B 44 (1988), 307–316.
E.L. Enriquez and S.R. Canoy Jr., On a variant of convex domination in a graph, Int. J. Math. Anal. 9 (2015), 1585–1592.
A. Gautam, B. Deb, and P. Dangal, P3-Convex Domination Number of a Graph, in Proceedings of the Eleventh International Conference on Mathematics and Computing (ICMC 2025), Lecture Notes in Networks and Systems, Vol. 1420, Springer, 2026.
F. Harary, Graph Theory, Wiley, New York, 1969.
F. Harary and J. Nieminen, Convexity in graphs, J. Differential Geom. 16 (1981), 185–190.
T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Topics in Domination in Graphs, Springer, Cham, 2020.
M.A. Henning, D. Rautenbach, and P.M. Schafer, Open packing, total domination, and the P3-Radon number, Discrete Math. 313 (2013), 992–998.
S.M. Hosamani, S. Shirkol, P.B. Jinagouda, and M. Krzywkowski, Degree equitable restrained double domination in graphs, Electron. J. Graph Theory Appl. 9 (2021), 105–111.
J. Kratica, V. Filipović, D. Matić, and A. Kartelj, An integer linear programming formulation for the convex dominating set problems, arXiv (2019), arXiv:1904.02541.
M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004), 181–188.
G. MacGillivray, C.M. Mynhardt, and V. Virgile, Eternal domination and clique covering, Electron. J. Graph Theory Appl. 10 (2022), 603–624.
I.M. Pelayo, Geodesic Convexity in Graphs, Springer, New York, 2013.
J. Raczek, NP-completeness of convex and weakly convex dominating set decision problems, Opuscula Math. 24 (2004), 189–196.
J. Raczek and M. Lemańska, A note on the weakly convex and convex domination numbers of a torus, Discrete Appl. Math. 158 (2010), 1708–1713.
E. Sampathkumar and S.B. Chikkodimath, Semitotal graphs of a graph–II, J. Karnatak Univ. 18 (1973), 274–280.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.