ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 9 (2015) 19-25
Partial product of graphs and Vizing's conjecture
Ismael González Yero
Departamento de Matemáticas, Escuela Politécnica Superior de Algeciras Universidad de Cadiz, Av. Ramon Puyol s/n, 11202 Algeciras, Spain
Received 9 December 2012, accepted 19 December 2013, published online 5 June 2014
Abstract
Let G and H be two graphs with vertex sets V1 = {ui,...,uni} and V2 = {vi,...,vn2}, respectively. If S c V2, then the partial Cartesian product of G and H with respect to S is the graph GDSH = (V, E), where V = Vi x V2 and two vertices (uj, vj) and (uk, v;) are adjacent in GDSH if and only if either (u = uk and Vj ~ v;) or (u ~ uk and Vj = v; € S). If A c V1 and B c V2, then the restricted partial strong product of G and H with respect to A and B is the graph GA H = (V, E), where V = V1 x V2 and two vertices (uj, vj) and (uk, v;) are adjacent in GA H if and only if either (uj = uk and vj ~ v;) or (uj ~ uk and vj = v;) or (uj € A, uk € A, vj € B, v; € B, uj ~ uk and vj ~ v;) or (uj € A, uk € A, vj € B, v; € B, uj ~ uk and vj ~ v;). 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.
Keywords: Domination, partial product of graphs, Cartesian product graph, strong product graph, Vizing's conjecture.
Math. Subj. Class.: 05C69, 05C70, 05C76
1 Introduction
Vizing's conjecture [7] is perhaps one of the most popular open problems related to domination in graphs. It states that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. A high quantity of approaches to that problem have been developed in this sense. The surveys [1, 3] are very complete compilations of the principal results obtained in this topic. Moreover, several Vizing-like results for some other kind of product graphs have been also published [5]. In
E-mail address: ismael.gonzalez@uca.es (Ismael Gonzalez Yero)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
20
Ars Math. Contemp. 9 (2015) 93-107
this article we introduce the notion of partial Cartesian product of graphs and obtain some corresponding Vizing-like results for the domination number and independence domination number of partial Cartesian product of graphs.
We establish first the principal terminology and notation which we will use throughout the article. Hereafter G = (V, E) denotes a finite simple graph. The complement of a set D is denoted by D. A set D is a dominating set if every vertex of D is adjacent to a vertex of D [4]. A dominating set D is called minimal if does not contain any dominating set as a proper subset. The domination number, y(G), is the minimum cardinality of any dominating set in G. We say that a set S is a Y(G)-set if it is a dominating set and |S| = y(G). The following result, due to Ore, can be found in [4].
Lemma 1.1. [4] A dominating set S is a minimal dominating set of a graph G = (V, E) if and only if for each u G S one of the following conditions holds:
•	u is an isolated vertex of S,
•	there exists v G V — S for which N(v) n S = {u}.
2 Results
Let G and H be two graphs with set of vertices V1 = {uL,...,uni} and V2 = {vi,...,v„2}, respectively. We recall that the Cartesian product of G and H is the graph GDH = (V, E), where V = V1 x V2 and two vertices (uj, vj) and (uk, v;) are adjacent in GDH if and only if one of the following conditions is satisfied:
•	u = uk and vj ~ v;, or
•	u ~ uk and vj = v;.
The strong product of G and H is the graph G K H = (V, E), where V = Vl x V2 and two vertices (u, vj) and (uk, v;) are adjacent in G K H if and only if one of the following conditions is satisfied:
•	u = uk and vj ~ v;, or
•	u ~ uk and vj = v;, or
•	u ~ uk and vj ~ v;.
For a vertex u G V1, the subgraph of GDH or G K H induced by the set {(u4, v)|v G V2} is called an H-layer or an H-fiber. Similarly, for vj G V2, the subgraph induced by
{(u, vj) |u G V1} is a G-layer or a G-fiber.
2.1 Partial Cartesian product of graphs
Let G and H be two graphs with set of vertices V = |ui,...,u„2} and V2 = jvi,...,vni}, respectively. If S c V2, then the partial Cartesian product of G and H with respect to S is the graph GDSH = (V, E), where V = V1 x V2 and two vertices (u^ vj) and (uk, v;) are adjacent in GDSH if and only if one of the following conditions is satisfied:
•	uj = uk and vj ~ v;, or
•	Uj ~ uk and vj = v; G S.
I. Gonzalez Yero: Partial product of graphs and Vizing's conjecture
21
Figure 1: The partial Cartesian product graph P4Drvi,v3}P4.
An example of a partial Cartesian product graph is shown in Figure 1. Also notice that the partial Cartesian product of G and H is the spanning subgraph of GDH obtained by deleting the edges of GDH in the H-fibers that correspond to vertices from V2 \ S.
Notice that if S = V2, then GDSH is the standard Cartesian product graph GDH. Also, note that if S is formed by only one vertex v, then GDSH is a particular case of the rooted product graph G ov H defined in [2]. Domination related parameters of rooted product graphs were studied in [6].
Theorem 2.1. Let G be a graph of order n and let H be any graph. If S is a subset of vertices of H, then
7 (GUIs H ) > n7 (H ) - n|S | + |S |7 (G).
Proof. Let Vi = {u,u2, ...,un} and V2 be the vertex sets of G and H, respectively. Hence, we consider the set of vertices S c V2. Let D be a 7(GDSH)-set. For every ui G V1, let Di = {v G V2 : (u, v) G D} and let Xi c Di be the set of vertices of H not dominated by Di. Hence, we have that Di U Xi is a dominating set in H and, as a consequence, 7(H) < |Di| + |Xi| for every is i G {1,..., n}. Hence,
iDI = jr iDi |
i= 1 n
> j(7(H) -|Xi|)
i=i
n
= nY(H) - j |Xi|.
i=i
Thus, we have that
n
7(GDsH) > nY(H) - j |Xi|.	(2.1)
i=i
Notice that if Xj = 0 for some j G {1, ...,n}, then there exists a vertex v G V2 such that (uj ,v) is dominated by a vertex (m ,v) G D with l = j. Thus, v G S. Hence, for every vertex w G S let Dw = {ui G Vi : (ui,w) G ({ui} x Xi)}. Notice that
22
Ars Math. Contemp. 9 (2015) 93-107
Dw is a dominating set in G. So, y(G) < |Dw| = n - |Dw|. Moreover, we have that
EHi |Xi| = Ewes |Dw|.
Now, by using (2.1) we have the following.
n
7(gDsH) > n7(H) - £ |Xi|
i=1
= n7(H) - £ |Dw|
wes
> n7(H) - £ (n - 7(G))
n ■
wes
n7(H) - n|S| + |S|y(G).
□
By taking a 7(H)-set S in the above theorem we obtain a Vizing-like result for the domination number of the partial Cartesian product graph GDSH with respect to S.
Corollary 2.2. Let G and H be any graphs. Then there exists a set S of vertices of H such that
Y(GDsH) > y(G)Y(H).
To see that the above bound is tight we consider the following. We say that a graph G = ( V, E) satisfies property P if it has a Y(G)-set D such that D = X U Y, X n Y = 0, X dominates V - Y and Y dominates V - X. Let F be the family of all graphs satisfying property P.
Proposition 2.3. Let G be a graph with domination number half its order and let H be a graph of the family F. Then there exists a set S of vertices of H such that
Y (GDs H ) = Y(G)Y (H ).
Proof. Since H = (V, E ) is a graph of the family F, there exists a y (H )-set S such that S = X U Y, X n Y = 0, X dominates V - Y and Y dominates V - X. Also, as G has domination number n, where n is the order of G, we have that there exists a y(G)-set D, such that y(G) = |D| = |D| = f. Notice that the set (D x X) U (D x Y) is a dominating set in GDS H and, as a consequence,
Y(GDsH) < |(D x X) U (D x Y)| = |D||X| + |D||Y| = nY^H) = y(G)y(H).
The proof is finished by Corollary 2.2.	□
Since for every set S of vertices of a graph H, the partial Cartesian product graph GDSH is a subgraph of the Cartesian product graph GDH, we have that y(GDsH) > Y (GDH ). Hence, notice that if there exists a graph GDs H such that y (GDs H ) = Y(G)y(H) and y(GDsH) > y(GDH), then the Vizing's conjecture is not true. In this sense, the above results lead to the following question.
Question: Are there some graphs G and H such that some set S of vertices of H satisfies that y(GDsH) = y(G)y(H) and y(GDsH) > y(GDH)?
I. Gonzalez Yero: Partial product of graphs and Vizing's conjecture
23
Next we study the independence domination number of the partial Cartesian product of graphs. A set Y is an independent dominating set in a graph G, if Y is a dominating set and there no edge between any two vertices of Y. The minimum cardinality of an independent dominating set of G is the independence domination number of G and it is denoted by ¿(G). The following result from [6] will be useful to present our results.
Lemma 2.4. [6] Let G = (V, E) be a graph. Then for every set of vertices A c V,
¿(G - A) > ¿(G) - |A|.
Theorem 2.5. Let G be a graph of order n and let H be any graph. If S is a subset of vertices of H, then
¿(GIUSH) > n(i(H) - |S|) + |S|i(G).
Proof. Let Vi = {w^ w2,..., wn} and V2 be the vertex sets of G and H, respectively, and let S c V2. Let Y be an ¿(GDSH)-set. For every « g V1, we define the following subsets of vertices of H:
•	Yi = {v G V2 : (ui,v) G Y},
•	Sj c S such that for every v G Sj, (m,, v) is independently dominated by some vertex (m,, v') G Y with v' G Yj,
•	R c S such that R = S n Y,.
Thus, we have that for every ¿ G {1,..., n}, Y is an independent dominating set in (V2 -
S + Rj + Sj). So, by Lemma 2.4 we have that |Y| > ¿((V2 - S + Rj + Sj)) > ¿(H) -|S| + |Rj| + |Sj|. Therefore, we obtain that
n	n	n
|Y| = £ |Yj|> ^(¿(H)-|S| + |Rj| + |Sj|)= n(¿(H)-|S|) + £(|R| + |Sj|). (2.2)
j=i j=i j=i
Now, for every vertex v G S we define the following subset of vertices of G:
•	Av = {w G Vi : («j, v) G Y},
•	Bv = {w G Vi : such that for every w g Bv, (wj,v) G Sj}, i.e., («, v) is independently dominated by some vertex (m,, v') where v' G Yj.
Thus, we have that Av is an independent dominating set in (Vi - Bv) and, by Lemma 2.4, we have that |Av| > ¿((Vi - Bv)) > ¿(G) - |Bv|. Moreover, notice that J]n=i(|Rj| + |Sj|) = J2ves(|Av | + |Bv |). So, from Equation 2.2 we have the following.
n
|Y|> n(¿(H) -|S|) + £(|R| + |Sj|)
j=i
= n(¿(H) - |S|) + £(|Av| + |Bv|)
ves
> n^(H) - |S|) + ^(¿(G) -|Bv| + |Bv|)
ves
= n(¿(H) - |S|) + |S|¿(G). Therefore, the result follows.	□
24
Ars Math. Contemp. 9 (2015) 93-107
Notice that, if S is an ¿(H)-set, then the above result leads to item (i) of the next corollary . Moreover, if S is formed by a single vertex, then the above result leads to a lower bound for the independence domination number of rooted product graphs, which was also obtained in [6].
Corollary 2.6. Let G be a graph of order n and let H be any graph with vertex set V. Let
s c v .
•	If S is an i(H)-set, then ¿(GDSH) > ¿(G)i(H).
•	If S = {v}, then ¿(GDSH) = i(G o^ H) > n(i(H) - 1) + ¿(G).
2.2 Partial strong product of graphs
Now, if A c Vl and B c V2, then the partial strong product of G and H with respect to A and B is the graph G KAjB H = (V, E), where V = V x V2 and two vertices (u, vj) and (uk, v;) are adjacent in G KAjB H if and only if one of the following conditions is satisfied:
•	ui = uk and vj ~ v;,
•	ui ~ uk and vj = v;,
•	ui € A, vj € B, ui ~ uk and vj ~ v;,
•	uk € A, v; € B, ui ~ uk and vj ~ v;.
Notice that if A = VL and B = V2, then G KUjB H is the standard strong product graph G Kl H .A more restrictive condition on the partial strong product of graphs could be the following one. If A c VL and B c V2, then the restricted partial strong product of G and H with respect to A and B is the graph G AKB H = (V, E), where V = VL x V2 and two vertices (ui, vj) and (uk, v;) are adjacent in G AKB H if and only if one of the following conditions is satisfied:
•	ui = uk and vj ~ v;,
•	ui ~ uk and vj = v;,
•	ui € A, uk € A, vj € B, v; € B, ui ~ uk and vj ~ v;,
•	ui € A, uk € A, vj € B, v; € B, ui ~ uk and vj ~ v;.
An example of a restricted partial strong product graph is shown in Figure 2.
Lemma 2.7. Let G, H be any graphs and let A (respectively B) be a j(G)-set (respectively Y(H)-set). Then A x B is a minimal dominating set in G AKB H.
Proof. The proof follows from Lemma 1.1 and the procedure of construction of the restricted partial strong product of graphs.	□
We omit the proof of the following result, since it is straightforward.
Theorem 2.8. Let G, H be any graphs. If A and B are dominating sets in G and H, respectively, then
Y (G Ka,b H) < y (G)y(H) and y(G a Kb H) < y (G)y(H ).
I. Gonzalez Yero: Partial product of graphs and Vizing's conjecture
25
V'	•
v,	O
v,	o
v,	#
U	U 2	1/3	U 4
Figure 2: The restricted partial strong product graph P4 {U1 ,u3} Kl{v2 ,v4} P4.
It is straightforward to observe that the partial Cartesian product graph GdSH with respect to any set of vertices S of G is a subgraph of the restricted partial strong product graph G A\JBH for any 7(G)-set A and any 7(H)-set B. Thus, according to results of Theorem 2.1, Corollary 2.2 and Theorem 2.8 there would exist a spanning subgraph F of the restricted partial strong product graph G AH satisfying that 7(F) = 7(G)y(H). In this sense, the question is: Is always the Cartesian product graph G\H a spanning subgraph of the graph F? If yes, then Vizing's conjecture is true.
References
[1]	B. Bresar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. KlavZar and D. F. Rall, Vizing's conjecture: a survey and recent results, Journal of Graph Theory 69 (2012), 46-76.
[2]	C. D. Godsil and B. D. McKay, A new graph product and its spectrum, Bulletin of the Australasian Mathematical Society 18 (1) (1978), 21-28.
[3]	B. Hartnell and D. F. Rall, Domination in Cartesian products: Vizing's conjecture. In Domination in graphs, volume 209 of Monography and Textbooks in Pure and Applied Mathematics, pages 163-189, Marcel Dekker, New York, 1998.
[4]	T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
[5]	R. Hammack, W. Imrich and S. KlavZar, Handbook of product graphs, volume 66 of Discrete Mathematics and its Applications, CRC Press, 2011.
[6]	D. Kuziak, M. Lemamka and I. G. Yero, Domination related parameters in rooted product graphs, Bulletin of the Malaysian Mathematical Sciences Society (2013), in press.
[7]	V. G. Vizing, The Cartesian product of graphs, Vycisl. Sistemy 9 (1963), 30-43.