Partial product of graphs and Vizing's conjecture

english

2015

volume 9, issue 1

Cartesian product graph   domination   partial product of graphs   strong product graph   Vizing's conjecture

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Let ?$G$? and ?$H$? be two graphs with vertex sets ?$V_1 = \{u_1, \dots, u_{n_1}\}$? and ?$V_2 = \{v_1, \dots, u_{n_2}\}$?, respectively. If ?$S \subset V_2$?, then the partial Cartesian product of ?$G$? and ?$H$? with respect to ?$S$? is the graph ?$G \Box_SH = (V,E)$?, where ?$V = V1 \times V_2$? and two vertices ?$(u_i, v_j)$? and ?$(u_k,v_j)$? are adjacent in ?$G \Box_SH$? if and only if either ?$(u_i = u_k \text{ and } v_j \sim v_l)$? or ?$(u_i \sim u_k \text{ and } v_j = v_l \in S)$?. If ?$A \subset V_1$? and ?$B \subset V_2$?, then the restricted partial strong product of ?$G$? and ?$H$? with respect to ?$A$? and ?$B$? is the graph ?$G_A \boxtimes_B H = (V,E)$?, where ?$V = V_1 \times V_2$? and two vertices ?$(u_i, v_j)$? and ?$(u_k,v_l)$? are adjacent in ?$G_A \boxtimes_B H$? if and only if either ?$(u_i = u_k \text{ and } v_j \sim v_l)$? or ?$(u_i \sim u_k \text{ and } v_j = v_l)$? or ?$(u_i \in A, u_k \notin A, v_j \in B, v_l \notin B, u_i \sim u_k \text{ and } v_j \sim v_l)$? or ?$(u_i \notin A, u_k \in A, v_j \notin B, v_l \in B, u_i \sim u_k \text{ and } v_j \sim 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.

29.05.2020