Previous |  Up |  Next


convex dominating set; convex domination number; clique dominating set; composition; Cartesian product
In this paper we characterize the convex dominating sets in the composition and Cartesian product of two connected graphs. The concepts of clique dominating set and clique domination number of a graph are defined. It is shown that the convex domination number of a composition $G[H]$ of two non-complete connected graphs $G$ and $H$ is equal to the clique domination number of $G$. The convex domination number of the Cartesian product of two connected graphs is related to the convex domination numbers of the graphs involved.
[1] Buckley, F., Harary, F.: Distance in Graphs. Addison-Wesley, Redwood City (1990). Zbl 0688.05017
[2] S. R. Canoy, Jr., I. J. L. Garces: Convex sets under some graph operations. Graphs Comb. 18 (2002), 787-793. DOI 10.1007/s003730200065 | MR 1964797 | Zbl 1009.05054
[3] Chartrand, G., Zhang, P.: Convex sets in graphs. Congr. Numerantium 136 (1999), 19-32. MR 1744171 | Zbl 0967.05031
[4] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998). MR 1605684 | Zbl 0890.05002
[5] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Domination in Graphs. Advanced Topics. Marcel Dekker, New York (1998). MR 1605685 | Zbl 0883.00011
[6] Lemańska, M.: Weakly convex and convex domination numbers. Opusc. Math. 24 (2004), 181-188. MR 2100881 | Zbl 1076.05060
Partner of
EuDML logo