Partial product of graphs and Vizing's conjecture

作者：Gonzalez Yero Ismael

来源：Ars Mathematica Contemporanea, 2015, 9(1): 19-25.

• Domination
• partial product of graphs
• Cartesian product graph
• strong product graph
• Vizing's conjecture

Let G and H be two graphs with vertex sets V-1 = {u(1) , ..., u(n1)} and V-2 = {v(1) , ..., v(n2)}, respectively. If S subset of V-2, then the partial Cartesian product of G and H with respect to S is the graph G square H-S = (V, E), where V = V-1 x V-2 and two vertices (u(i), v(j)) and (u(k), v(l)) are adjacent in G square H-S if and only if either (u(i) = u(k) and v(j) similar to v(l)) or (u(i) similar to u(k) and v(j) = v(l) epsilon S). If A subset of V-1 and B subset of V-2, then the restricted partial strong product of G and H with respect to A and B is the graph G(A) boxed times(B) H = (V, E), where V = V-1 x V-2 and two vertices (u(i), v(j)) and (u(k), v(l)) are adjacent in G(A) boxed times(B) H if and only if either (u(i) = u(k) and v(j) similar to v(l)) or (u(i) similar to u(k) and v(j) = v(l)) or (u(i) epsilon A, u(k) is not an element of A, v(j) epsilon B, v(l) is not an element of B, u(i) similar to u(k) and v(j) similar to v(l)) or (u(i) is not an element of A, u(k) epsilon A, v(j) is not an element of B, v(l) epsilon B, u(i) similar to u(k) and v(j) similar to v(l)). In this article we obtain Vizing-like results for the domination number and the independence domination number of the partial Cartesian product of graphs. Moreover we study the domination number of the restricted partial strong product of graphs.

• 出版日期2015