Outer-weakly convex domination number of graphs

Document Type : Original paper


1 University of San Jose-Recoletos

2 University of Cebu

3 Cebu Technological University-San Fernando Extension


For a given simple graph $G=(V,E)$, a set $S\subseteq V$ is an outer-weakly convex dominating set if every vertex in $V\setminus S$ is adjacent to some vertex in $S$ and $V\setminus S$ is a weakly convex set. The \emph{outer-weakly convex domination number} of a graph $G$, denoted by $\widetilde{\gamma}_{wcon}(G)$, is the minimum cardinality of an outer-weakly convex dominating set of $G$. In this paper, we initiate the study of outer-weakly convex domination as a new variant of graph domination and we show the close relationship that exists between this novel parameter and other domination parameters of a graph. Furthermore, we obtain general bounds on $\widetilde{\gamma}_{wcon}(G)$ and, for some particular families of graphs, we obtain closed formula. 


Main Subjects

[1] M.H. Akhbari, R. Hasni, O. Favaron, H. Karami, and S.M. Sheikholeslami, On the outer-connected domination in graphs, J. Comb. Optim. 26 (2013), no. 1, 10–18.
[2] G. Chartrand and P. Zhang, Convex sets in graphs, Congr. Numer. 136 (1999), 19–32.
[3] J. Cyman, The outer-connected domination number of a graph, Australas. J. Combin. 38 (2007), 35–46.
[4] J.A. Dayap, Outer-convex domination in the corona of graphs, TWMS Journal of Applied and Engineering Mathematics, (to appear).
[5] J.A. Dayap, J.P. Dequillo, W.V. Rios, R.M.T. Telen, and A.Q. Sollano, Securing chemical formula using polyalphabetic affine cipher, Journal of Global Research in Mathematical Archives 6 (2019), no. 9, 6–14.
[6] J.A. Dayap, J.S. Dionsay, and R.T. Telen, Perfect outer-convex domination in graphs, International Journal of Latest Engineering Research and Applications 3 (2018), no. 7, 25–29.
[7] J.A. Dayap and E.L. Enriquez, Outer-convex domination in the composition and cartesian product of graphs, Journal of Global Research in Mathematical Archives 6 (2019), no. 3, 34–41.
[8] J.A. Dayap and E.L. Enriquez, Outer-convex domination in graphs, Discrete Math. Algorithms Appl. 12 (2020), no. 1, Article ID: 2050008.
[9] M. Dettlaff, M. Lemańska, S. Kosary, and S.M. Sheikholeslami, The convex domination subdivision number of a graph, Commun. Comb. Optim. 1 (2016), no. 1, 43–56.
[10] E. Enriquez, V. Fernandez, T. Punzalan, and J.A. Dayap, Perfect outer-connected domination in the join and corona of graphs, Recoletos Multidisciplinary Research Journal 4 (2016), no. 2, 1–8.
[11] F. Harary and J. Nieminen, Convexity in graphs, J. Differ Geom. 16 (1981), no. 2, 185–190.
[12] T.W. Haynes, S.T. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, CRC press, 1998.
[13] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
[14] M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004), no. 2, 181–188.