Convex domination in the composition and cartesian product of graphs - Labendia, Mhelmar A.; Canoy, Segio R. Jr. (2011)
The convex dominating sets in the composition and cartesian product of two connected graphs were characterized. It was shown that the convex domination number ycon (G[H]) of a composition G[H] of two non-complete connected graphs G and H is equal to the clique domination number ycl(G) of G. The convex domination number. Ycon (G x H) of the cartesian product of two connected graphs was also studied. It was found out that this number is related to the convex domination numbers of the graph involved. Some results in an earlier work on convexity were used to characterize the convex dominating sets in the composition and cartesian product of two connected graphs. the concept of cyclic domination number was also defined as this was needed to obtain an expression for the convex domination number of a composition of graphs. The following results were generated in the study:
1. Let G be a connected graph and Kn the complete graph of order n. A subset C=U{[{x}] x Tx]: x ϵ S} of V(G[Kn]) is convex dominating G[Kn] if and only if the S is convex dominating in G.
2. Let G be a connected graph and Kn the complete graph of order in n≥1. Then ycon (G[Kn]) = ycon (G).
3. Let G and H be connected non-complete graphs with ycl(G)≥2. Then a subset C=U{[{x}] x Tx]: x ϵ S} of V(G[H]) is convex dominating in G[H] if and only if the S is the S is a clique dominating set in G and Tx is a clique in H for every X ϵ S.
4. Let G and H connected and non-complete graphs with ycl (G)≥2. Then ycon (G[H])=ycl(G).
5. Let G and H be connected graphs of orders m and n, respectively. Then ycon(G x H)=min{n ycon (G), m ycon(H)}.
Keywords: Graphic methods