An Inequality Related to Vizing’s Conjecture

W. Edwin Clark and Stephen Suen

Department of Mathematics, University of South Florida, Tampa, FL 33620-5700, USA

                   eclark@math.usf.edu   suen@math.usf.edu

Submitted November 29, 1999; Accepted May 24, 2000

Abstract

Let γ(G) denote the domination number of a graph G and let G □ H denote the Cartesian product of graphs G and H. We prove that γ(G)γ(H) ≤ 2γ(G□H) for all simple graphs G and H.

2000 Mathematics Subject Classifications: Primary 05C69, Secondary 05C35

We use V (G), E(G), γ(G), respectively, to denote the vertex set, edge set and domination number of the (simple) graph G. For a pair of graphs G and H, the Cartesian product G □ H of G and H is the graph with vertex set V (G) × V (H) and where two vertices are adjacent if and only if they are equal in one coordinate and adjacent in the other. In 1963, V. G. Vizing [2] conjectured that for any graphs G and H,

γ(G)γ(H) ≤ γ(G □ H).  (1)

The reader is referred to Hartnell and Rall [1] for a summary of recent progress on Vizing’s conjecture. We note that there are graphs G and H for which equality holds in (1). However, it was previously unknown [1] whether there exists a constant c such that

γ(G)γ(H) ≤ c γ(G □ H).

We shall show in this note that γ(G)γ(H) ≤ 2 γ(G □ H).

For S ⊆ V (G) we let N_{G}[S] denote the set of vertices in V (G) that are in S or adjacent to a vertex in S, i.e., the set of vertices in V (G) dominated by vertices in S.

Theorem 1 For any graphs G and H,

γ(G)γ(H) ≤ 2γ(G □ H).

Proof. Let D be a dominating set of G □ H. It is sufficient to show that

γ(G)γ(H) ≤ 2|D|.  (2)

Let {u_{1}, u_{2}, …, u_{γ(G)}} be a dominating set of G. Form a partition {Π_{1}, Π_{2}, …, Π_{γ(G)}} of V (G) so that for all i: (i) u_{i} ∈ Π_{i}, and (ii) u ∈ Π_{i} implies u = u_{i} or u is adjacent to u_{i}. This partition of V (G) induces a partition {D_{1}, D_{2}, …, D_{γ(G)}} of D where

D_{i} = (Π_{i} × V (H)) ∩ D.

Let P_{i} be the projection of D_{i} onto H. That is,

P_{i} = {v | (u, v) ∈ D_{i} for some u ∈ Π_{i}}.

Observe that for any i, P_{i} ∪ (V (H) − N_{H}[P_{i}]) is a dominating set of H, and hence the number of vertices in V (H) not dominated by P_{i} satisfies the inequality

|V (H) − N_{H}[P_{i}]| ≥ γ(H) − |P_{i}|.  (3)

For v ∈ V (H), let

Q_{v} = D ∩ (V (G) × {v}) = {(u, v) ∈ D | u ∈ V (G)}.

and C be the subset of {1, 2, …, γ(G)} × V (H) given by

C = { (i, v) | Π_{i} × {v} ⊆ N_{G□H}[ Q_{v}] }.

Let N = |C|. By counting in two different ways we shall find upper and lower bounds for N. Let

L_{i} = {(i, v) ∈ C | v ∈ V (H)}, and
R_{v} = {(i, v) ∈ C | 1 ≤ i ≤ γ(G)}.

Clearly

N = ∑_{i=1}^{γ(G)} |L_{i}| = ∑_{v∈V (H)} |R_{v}|.

Note that if v ∈ V (H) − N_{H}[P_{i}], then the vertices in Π_{i} × {v} must be dominated by vertices in Q_{v} and therefore (i, v) ∈ L_{i}. This implies that |L_{i}| ≥ |V (H) − N_{H}[P_{i}]|. Hence

N ≥ ∑_{i=1}^{γ(G)} |V (H) − N_{H}[P_{i}]|

and it follows from (3) that

N ≥ γ(G)γ(H) − ∑_{i=1}^{γ(G)} |P_{i}|

≥ γ(G)γ(H) − ∑_{i=1}^{γ(G)} |D_{i}|.

So we obtain the following lower bound for N.

N ≥ γ(G)γ(H) − |D|.  (4)

For each v ∈ V (H), |R_{v}| ≤ |Q_{v}|. If not,

{ u | (u, v) ∈ Q_{v}} ∪ { u_{j} | (j, v) ∉ R_{v}}

is a dominating set of G with cardinality

|Q_{v}| + (γ(G) − |R_{v}|) = γ(G) − (|R_{v}| − |Q_{v}|) < γ(G),

and we have a contradiction. This observation shows that

N = ∑_{v∈V (H)} |R_{v}| ≤ ∑_{v∈V (H)} |Q_{v}| = |D|.  (5)

It follows from (4) and (5) that

γ(G)γ(H) − |D| ≤ N ≤ |D|,

and the desired inequality (2) follows.

References

[1] Bert Hartnell and Douglas F. Rall, Domination in Cartesian Products: Vizing’s Conjecture, in Domination in Graphs—Advanced Topics edited by Haynes, et al, Marcel Dekker, Inc, New York, 1998, 163–189.

[2] V. G. Vizing, The cartesian product of graphs, Vyčisl. Sistemy 9, 1963, 30–43.