Outer-convex Domination in the Composition and Cartesian Product of Graphs

Jonecis Adolfo Dayap, Enrico Limbo Enriquez


Let G be a connected simple graph. A set S of vertices of a graph G is an outer-convex dominating set if every vertex not in S is adjacent to some vertex in S and V (G) \ S is a convex set. In this paper we characterize the outer-convex dominating sets in the composition and Cartesian product of two connected graphs. It is shown that the outer-convex domination number of a composition G[H] of two connected graphs G = Pm (m ≥ 3) and H = Kn (n ≥ 2) is equal to 2 if m = 3 and n(m − 4) + 2 if m > 3. The outer-convex domination number of the Cartesian product G□H of two non-complete connected graphs G and H depends on the outer-convex domination number of G and H.

Full Text:



Haynes, T. W., Hedetniemi, S., & Slater, P. (1998). Fundamentals of domination in graphs. CRC Press.

Dayap, J. A., & Enriquez, E.L.(2017). Outer-convex Domination in Graphs. Manuscript submitted for publication.

Cockayne, E. J., & Hedetniemi, S. T. (1977). Towards a theory of domination in graphs. Networks, 7(3),247-261.

Ore, O. (1962). Theory of Graphs (Vol. 38). American Mathematical Society.

Harary, F., & Nieminen, J. (1981). Convexity in graphs. Journal of Differential Geometry, 16(2), 185-190.

Chartrand, G., & Zhang, P. (1999). Convex sets in graphs. In Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999). Congr. Numer. (Vol. 136, pp. 19-32).

Canoy Jr, S.R., & and Garces, I. J. L. (2002). Convex sets under some graph operations. Graphs and Combinatorics, 18(4), 787-793.

Enriquez, E. L., & Canoy Jr, S. R. (2015). Secure convex domination in a graph. International Journal of Mathematical Analysis, 9(7), 317-325.

M. Lemanska, Weakly convex and convex domination numbers. Opuscula Mathematica, 24 (2004), 181-188.

Labendia, M.A., Canoy, S.R. Convex Domination in the Composition and Cartesian Product of Graphs. Czechoslovak Mathematical Journal, 62(2012), 1003-1009.

Cyman, J. (2007). The outer1-connected domination number of a graph. Australasian journal of Combinatorics, 38, 35-46.9

Enriquez, E.L., Fernandez, V., Punzalan, T., & Dayap, J.A. (2017). Perfect outer-connected domination in the join and corona of graphs. Recoletos Multidisciplinary Research Journal, 4(2).

Cyman, J. (2010). Total outer-connected domination in trees. Discussiones Mathematicae Graph Theory,

(3), 377-383.

Favaron, O., Karami, H., & Sheikholeslami, S. M. (2014). On the total outer-connected domination in graphs. Journal of Combinatorial Optimization, 27(3), 451-461.

Hinampas Jr, R. G., Lomarda-Hinampas, J., & Dahunan, A. R. (2017). 1-movable Independent Outer-connected Domination in Graphs. Global Journal of Pure and Applied Mathematics, 13(1), 41-49.

Dayap, J.A., Dionsay, J.S., & Telen, R.T. (2018). Perfect outer-convex domination in graphs. International Journal of Latest Engineering Research and Applications, 3(7), 25-29.

Chartrand, G., & Zhang, P. (2013). A first course in graph theory.Courier Corporation


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.


Free Web Counter