An Algebraic Exploration of Dominating Sets

and Vizings Conjecture

S. Margulies
Department of Mathematics
Pennsylvania State University
State College, PA
margulies@math.psu.edu
I. V. Hicks
Computational and Applied Mathematics
Rice University
Houston, TX
ivhicks@rice.edu
Submitted: Oct 7, 2011; Accepted: Mar 29, 2012; Published: Apr 7, 2012
Mathematics Subject Classications: 05C69, 13P10
Abstract
Systems of polynomial equations are commonly used to model combinatorial
problems such as independent set, graph coloring, Hamiltonian path, and others.
We formulate the dominating set problem as a system of polynomial equations in
two dierent ways: rst, as a single, high-degree polynomial, and second as a col-
lection of polynomials based on the complements of domination-critical graphs. We
then provide a sucient criterion for demonstrating that a particular ideal represen-
tation is already the universal Grobner bases of an ideal, and show that the second
representation of the dominating set ideal in terms of domination-critical graphs
is the universal Grobner basis for that ideal. We also present the rst algebraic
formulation of Vizings conjecture, and discuss the theoretical and computational
ramications to this conjecture when using either of the two dominating set repre-
sentations described above.
Keywords: dominating sets, Vizings conjecture, universal Grobner bases
1 Introduction
The combination of non-linear models and techniques from computer algebra is gaining
acceptance as a tool for exposing combinatorial properties of graph-theoretic problems.
For example, prior work on polynomial encodings includes colorings [3, 13, 18, 21, 23,
24, 25, 27, 28, 30], stable sets [20, 21, 25, 31], matchings [14], and ows [3, 29, 30].
These non-linear encodings have been used to prove combinatorial results [2, 22, 24], and
Gr obner bases have been the building blocks of algorithms for solving integer programs
[6, 10, 34], but techniques from computer algebra are not widely used by combinatorists
and graph theorists, and thus have not yet been deeply explored. In this paper, we move
the electronic journal of combinatorics 19(2) (2012), #P1 1
beyond simply formulating a graph-theoretic problem as a system of polynomial equations,
and instead formulate an entire graph-theoretic conjecture using systems of polynomial
equations and algebraic techniques. Although the method we introduce here can probably
be applied to other open questions involving inequalities, we focus on the dominating set
problem and an algebraic approach to a famous open question from domination theory:
Vizings conjecture.
Given a graph G, a set D V (G) is a dominating set if for all v / D, there is a u D
such that v is adjacent to u in G. The domination number of G, denoted by (G), is the
size of a minimum dominating set in G. The decision problem of determining whether a
given graph has a dominating set of size k is NP-complete [15]. Given graphs G and H,
the Cartesian product graph GH has vertex set V (G) V (H), and edge set
E(GH) =
_
(gh, g

) : g = g

and (h, h

) E(H), or h = h

and (g, g

) E(G)
_
,
where g, g

V (G) and h, h

V (H). In 1968, V. Vizing conjectured a beautiful rela-

tionship between domination numbers and Cartesian product graphs:
Conjecture 1 (Vizing [35], 1968). Given graphs G and H, (G)(H) (GH).
Vizings conjecture is an active area of research spanning over forty years. Early results
have focused on proving the conjecture holds for a certain classes of graphs. For example,
in 1979, Barcalkin and German [5] proved that Vizings conjecture holds for graphs sat-
isfying a certain partitioning condition on the vertex set. The idea of a partitioning
condition inspired work for the next several decades, as Vizings conjecture was shown to
hold on paths, trees, cycles, chordal graphs, graphs satisfying certain coloring properties,
and graphs with (G) 2. These results are clearly outlined in the 1998 survey paper by
Hartnell and Rall [17]. In 2000, Clark and Suen [9] showed that (G)(H) 2(GH),
and in 2004, L. Sun [33] showed that Vizings conjecture holds on graphs with (G) 3.
Finally, in 2009, Hartnell and Rall, et al. [7] contributed another thorough survey pa-
per summarizing the work from 1968 to 2008, which contains new results, new proofs of
existing results, and comments about minimal counter-examples.
Vizings conjecture is of great interest to graph theorists for two primary reasons. First,
it is an easily stated, easily understood combinatorial problem whose proof has eluded
demonstration for decades. Second, it is of algorithmic interest, since domination in
graphs has applications ranging from optimal re station placement to wireless networks
(see survey [7]), and additionally, product graphs are a common algorithmic tool for
studying the scaling of NP-hard graph-theoretic invariants. In short, an elegant, elusive
conjecture with algorithmic consequences will always excite exploration.
We begin by reviewing basic ideas from algebraic geometry: unions of varieties, inter-
sections of ideals, notions of radical ideals, and universal Grobner bases (Sections 2 and 3).
In Section 3, for certain ideals, we develop a criterion for identifying a particular basis of
the ideal as the universal Gr obner basis. In Section 4.1, we represent both the problem of
nding graphs G with dominating sets of size k, and the problem of nding graphs G and
H with dominating sets of size k, l respectively such that the Cartesian product graph
GH has a dominating set of size r, as systems of polynomial equations. In Section 4.2,
the electronic journal of combinatorics 19(2) (2012), #P1 2
we develop the idea of k-domination-covers, or k-covers, which are the complements of
k-dominating graphs. We identify specic properties of k-covers, which translate to new
properties of domination-critical graphs.
In Section 4.3, we unify the seemingly disparate results that have appeared thus far
in our paper: we prove that the same ideals described in Section 4.1 can be represented
by a set of polynomials based on k-covers, that is, by a set of polynomials based on the
complements of domination-critical graphs. By the results in Section 3, we demonstrate
that this representation is the universal Grobner basis of the ideal.
Our paper culminates in Section 5 with an algebraic representation of Vizings conjec-
ture. This representation is built upon the union of certain varieties and the intersection
of certain ideals. We initially present the algebraic version of Vizings conjecture without
respect to a particular representation. We then discuss the consequences of using either
of the two representations presented in Sections 4.1 and 4.3. We include comments about
computational results and future computational directions, as well as approaches from
a purely graph theory perspective. We conclude by clarifying the relationship between
universal Gr obner bases and Vizings conjecture via k-covers, and reclaim a known result
where Vizings conjecture holds.
2 Algebraic Denitions and Background
In this section, we outline the basic denitions and results concerning ideals and varieties
that are utilized throughout the paper, and that are particularly necessary for the alge-
braic approach to Vizings conjecture described in Section 5. The results presented in this
section are well-known in the eld of algebraic geometry and are presented in detail in [11],
Chapters 2 and 4. The only new contribution is Lemma 3, which is a small application
of well-known results. The ideals referenced throughout are always ideals in polynomial
rings, i.e. I K[x
1
, . . . , x
n
], where K is an algebraically-closed eld. In our case, K = C.
Given a system of polynomial equations, f
1
= f
2
= = f
s
= 0, the ideal associated
with the system is I = f
1
, . . . , f
s
, and the variety associated I (i.e. V (I)) is the set of
common zeros of f
1
, . . . , f
s
. In other words, V (I) = x C
n
: f
1
(x) = = f
s
(x) = 0.
An ideal is zero-dimensional if V (I) is nite. Throughout the paper, we will often write a
polynomial f I as

()f
i
. In this case, () represents the coecients of the generators
f
i
, but because we do not refer to the coecients explicitly, we do not need to give them
individual and precise labels such as a
i
.
Given two ideals, I = f
1
, . . . , f
s
and J = g
1
, . . . , g
t
, the product ideal I J is the
ideal generated by all polynomials f g with f I and g J. It can be shown ([11], pg
183, Prop. 6) that I J (often denoted by IJ) is the ideal generated by f
i
g
j
: 1 i
s, 1 j t. We summarize the results concerning the varieties of I and J as follows:
V (I) V (J) = V (f
i
g
j
: 1 i s, 1 j t) = V (I J) = V (I J).
An ideal I is radical if f
m
I, for some integer m 1, implies that f I. Given an
ideal I, the radical of I, denoted

I, is the set f : f
m
I for some integer m 1. It
the electronic journal of combinatorics 19(2) (2012), #P1 3
is easy to see that an ideal I is radical if and only if I =

I. We recall the following fact

concerning product ideals and radical ideals (left as an exercise in [11]): Given radical
ideals I, J K[x
1
, . . . , x
n
],

IJ = I J. We note that in one particular case, it is trivial

to determine whether or not an ideal is radical.
Lemma 2. ([19], Section 3.7.B, pg. 246) Given a zero-dimensional ideal I, if I contains
a univariate square-free polynomial in each variable, then I is radical.
In this case, square-free implies that when a polynomial is decomposed into its unique
factorization, there are no repeated factors. For example, (x
2
+y)(x
4
+2z +3) is square-
free, but (x
2
+y)(x
4
+2z+3)
3
is not. In particular, Lemma 2 implies that ideals containing
x
2
i
x
i
= x
i
(x
i
1) in each variable (i.e., the boolean ideals) are radical. In Section 4, we
will see that all ideals associated with dominating sets (and therefore Vizings conjecture)
are radical for this reason.
In general, it may be quite dicult to determine a basis for

IJ. However, if I and J

are radical ideals via Lemma 2, and additionally, if the univariate, square-free polynomials
in each variable contained in I, J are identical, we can explicitly determine a basis for

IJ.
Lemma 3. Let I and J be ideals such that I = f
1
, . . . f
s
and J = g
1
, . . . , g
t
. Fur-
thermore, for 1 i n, let f
i
= g
i
be square-free univariate polynomials in x
i
. Then

IJ = f
i
g
j
: 1 i s, 1 j t +f
i
: 1 i n.
Proof. We prove the inclusion in both directions. For convenience, let M := f
i
g
j
: 1
i s, 1 j t + f
i
: 1 i n. First, we show that

IJ M. Let h

IJ.
Then, there exists an integer m 1 such that h
m
IJ. Thus, h
m
=

()fg. Thus,
h
m
M. But, by Lemma 2, the ideal M is radical since M contains a square-free
univariate polynomial f
i
in each variable x
i
. Thus, h
m
M implies that h M.
Conversely, to show that M

IJ, let h M. Then, h =

()fg +

()f. Consider
h
2
=
_

()fg +

()f
__

()fg +

()f
_
.
Any term in the expanded h
2
can be viewed as ()f
i
g
j
f
k
g
l
= ()f
i
g
j
, or ()f
i
g
j
f
k
= ()f
i
g
j
,
or ()f
i
f
j
= ()f
i
g
j
, etc. Thus, any term in the expanded h
2
can be written as ()fg, with
any extra multiplicities in f or g simply folded into the coecient. Therefore,
h
2
=

()fg,
and there exists an integer m = 2 1 such that h
m
IJ, implying h

IJ.
This brings us to the following critical fact: if I and J are boolean, radical ideals, then
by Lemma 3,

IJ = f
i
g
j
: 1 i s, 1 j t +x
i
(x
i
1) : 1 i n = I J.
In Section 4, when we represent the dominating set problem as a system of polynomial
equations, the representations will be boolean, radical ideals as described above. Thus,
the basis of their product ideals can be described via Lemma 3. This fact will be vital in
Section 5 when we present an algebraic representation of Vizings conjecture.
the electronic journal of combinatorics 19(2) (2012), #P1 4
3 Universal Gr obner Bases and Linear Factors
In this section, we provide a brief overview of the terminology (from [11], Chap. 2) per-
taining to Grobner bases, and build o the ideas of De Loera in [21] to show that a specic
set of linear factor polynomials is a universal Grobner basis. These linear factor ideals
allow us to provide a combinatorial interpretation of the universal Gr obner basis of the
dominating set ideal dened in Section 4, and will be used in our algebraic exploration of
Vizings conjecture.
A monomial order for the monomials in the polynomial ring K[x
1
, . . . , x
n
] is a well-
ordering which is multiplicative, and for which the constant polynomial is the smallest.
The leading term lt(f) of a polynomial f K[x
1
, . . . , x
n
] is the largest monomial in f
(and its corresponding coecient) with respect to the monomial order . Given an ideal
I, a nite subset ( = g
1
, . . . , g
r
of I is a Grobner basis of I (with respect to ) if
lt

(g
1
), . . . , lt

(g
r
) = lt

(I) = lt

(f) : f I.
A nite subset ( of I is a universal Gr obner basis of I if it is Gr obner basis of I with respect
to any monomial order. Although there are innitely many monomial orderings, the
universal Gr obner basis of I is nite and unique (see [11] for further details). Buchbergers
S-pair criterion [8] is a specic criterion for determining if a given subset of polynomials is
a Grobner basis of I. In order to dene Buchbergers S-pair criterion, we x a monomial
order and recall the following notation:
f
F
denotes the remainder of division of the polynomial f by the ordered s-tuple
F = (f
1
, . . . , f
s
) (see [11], Chap. 2, Sec. 3 for details.)
Example: Note that (x
2
y + xy
2
+ y
2
)
{xy1,y
2
1}
= x + y + 1, since
x
2
y + xy
2
+ y
2
= (x + y)(xy 1) + (y
2
1) + x + y + 1,
but when the order of F is changed, (x
2
y + xy
2
+ y
2
)
{y
2
1,xy1,}
= 2x + 1, since
(x
2
y + xy
2
+ y
2
) = (x + 1)(y
2
1) + x(xy 1) + 2x + 1.
x

is the least common multiple of the leading monomial lm(f) and the leading
monomial lm(g), written as x

= lcm
_
lm(f), lm(g)
_
.
The S-pair of f and g is the combination:
S(f, g) =
x

lt(f)
f
x

lt(g)
g.
We will now characterize Gr obner bases in terms of S-pairs.
Theorem 4 ([8] (also see [11], Chap. 2, Sec. 6 for details)). Given an ideal I, a basis ( =
g
1
, . . . , g
r
of I is a Grobner basis for I, if and only if, for all pairs i ,= j, S(g
i
, g
j
)
G
= 0.
the electronic journal of combinatorics 19(2) (2012), #P1 5
We now construct a set of polynomials, where each polynomial is a product of linear
factors, and show that if the set satises the linear factor criterion, then the set is a
universal Gr obner basis. Let S = i
1
, i
2
, . . . , i
k
1, . . . , n, and
P(S) := (x
i
1
1)(x
i
2
1) (x
i
k
1), and x(S) = x
i
1
x
i
2
x
i
k
.
Denition 5. Let S
1
, . . . , S
D
be a set such that each S
i
1, . . . , n and [S
i
[ = d
i
. We
say that the set S
1
, . . . , S
D
satises the linear factor criterion if, for any integers i, j, k,
S
k
is a not a proper subset of S
i
S
i
S
j
, and S
k
is a not a proper subset of S
j
S
i
S
j
.
Theorem 6. Let S
1
, . . . , S
D
with S
i
1, . . . , n be a set that satises the linear
factor criterion, and let g
i
= P(S
i
). Then g
1
, . . . , g
D
is a universal Grobner basis of
g
1
, . . . , g
D
.
Before we prove this theorem, we present an example.
Example 7. Consider C[x
1
, . . . , x
12
], and let S
1
= 1, 2, 3, 5, 6, S
2
= 1, 2, 3, 7, 8, S
3
=
9, 10, 11, 12, S
4
= 4, 8, 9. Let ( = g
1
, g
2
, g
3
, g
4
with g
i
= P(S
i
).
g
1
:= (x
1
1)(x
2
1)(x
3
1)(x
5
1)(x
6
1),
g
2
:= (x
1
1)(x
2
1)(x
3
1)(x
7
1)(x
8
1),
g
3
:= (x
9
1)(x
10
1)(x
11
1)(x
12
1),
g
4
:= (x
4
1)(x
8
1)(x
9
1).
Since S
1
S
2
= 1, 2, 3, S
1
(S
1
S
2
) = 5, 6, and S
2
(S
1
S
2
) = 7, 8. Neither S
3
nor S
4
is a proper subset of S
1
(S
1
S
2
) or S
2
(S
1
S
2
). This is true for all i, j pairs,
thus S
1
, S
2
, S
3
, S
4
satises the linear factor criterion. Additionally, note that lt(g
i
) is
always x(S
i
), regardless of the specied monomial order. Thus, we see
S(g
2
, g
4
) =
x
1
x
2
x
3
x
4
x
7
x
8
x
9
x
1
x
2
x
3
x
7
x
8
g
2

x
1
x
2
x
3
x
4
x
7
x
8
x
9
x
4
x
8
x
9
g
4
= x
4
x
9
g
2
x
1
x
2
x
3
x
7
g
4
= (x
4
+ x
9
1)g
2
(x
1
x
2
x
3
+ x
1
x
2
x
7
+ x
1
x
3
x
7
+ x
2
x
3
x
7
x
1
x
2
x
1
x
3
x
1
x
7
x
2
x
3
x
2
x
7
x
3
x
7
+ x
1
+ x
2
+ x
3
+ x
7
1)g
4
.
Regardless of the monomial order, the leading terms of the coecients of g
2
and g
4
are
not divisible by the leading terms of g
1
, g
2
, g
3
or g
4
, Thus, S(g
2
, g
4
)
G
= 0. Performing
similar calculations for all other pairs can quickly show that g
1
, . . . , g
4
is the universal
Gr obner basis of g
1
, . . . , g
4
.
For simplicity of notation, let S
i
only
= S
i
(S
i
S
j
) and S
j
only
= S
j
(S
i
S
j
). Further-
more, let S
ij

be a subset of S
i
S
j
, S
i
only
be a subset of S
i
only
, and S
j
only
be a subset of
S
j
only
. Note that
[S
j
only
[ + d
i
= [S
i
only
[ + d
j
. (1)
the electronic journal of combinatorics 19(2) (2012), #P1 6
Proof. We will show that the set of generators ( = g
1
, . . . , g
D
satises Buchbergers
S-pair criterion. Consider any two polynomials g
i
, g
j
. We must show S(g
i
, g
j
)
G
= 0. We
claim
S(g
i
, g
j
) =
x(S
i
S
j
)
x(S
i
)
g
i

x(S
i
S
j
)
x(S
j
)
g
j
= x(S
j
only
)g
i
x(S
i
only
)g
j
(2)
=
_
lt
_
P(S
j
only
)
_
P(S
j
only
)
_
g
i

_
lt
_
P(S
i
only
)
_
P(S
i
only
)
_
g
j
. (3)
Before we prove the equality between lines 2 and 3, we note that, if true, we have
already shown that S(g
i
, g
j
)
G
= 0. This can be seen by noting that, since S
1
, . . . , S
D

satises the linear factor criterion, given integers i, j, k, S

k
is not a proper subset of S
i
only
and S
k
is not a proper subset of S
j
only
. Additionally, regardless of the monomial order, the
leading term of g
i
is x(S
i
), and the leading term of
_
lt
_
P(S
j
only
)
_
P(S
j
only
)
_
is a proper
subset of S
j
only
(similarly,
_
lt
_
P(S
i
only
)
_
P(S
i
only
)
_
is a proper subset of S
i
only
). Thus,
lt(g
k
) does not divide either
_
lt
_
P(S
j
only
)
_
P(S
j
only
)
_
or
_
lt
_
P(S
i
only
)
_
P(S
i
only
)
_
,
and we can see that S(g
i
, g
j
)
G
= 0.
In order to prove the equality between lines 2 and 3, we must show that every monomial
in line 2 either cancels within line 2, or appears in line 3 with the same coecient, and
vice versa.
Let x(M) be a monomial appearing in line 2. Either
M = S
j
only
S
ij

S
i
only
, or M = S
i
only
S
ij

S
j
only
.
We note that x(M) appears in both x(S
j
only
)g
i
and x(S
i
only
)g
j
only when S
i
only
= S
i
only
and S
j
only
= S
j
only
. In this case, the coecient for x(M) is (1)
C
(1)
D
where
C = d
i

_

S
ij

S
i
only

_
, and D = d
j

_

S
ij

S
j
only

_
.
This formula can be explained by noting that, in any polynomial that is the product
of linear factors, the coecient for a given monomial is (1)
C
where C is the degree of
the polynomial minus the degree of the given monomial. For example, consider f :=
(x
1
1)(x
2
1)(x
3
1)(x
7
1). The coecient for the monomial x
1
x
2
x
3
is (1)
43
= 1,
and the coecient for x
2
x
7
is (1)
42
= 1.
Using the identity given in Eq. 1, we note that d
i

S
i
only

= d
j

S
j
only

. Thus,
C = D, and the monomial cancels.
We will now consider the case where M = S
j
only
S
ij

S
i
only
and S
i
only
,= S
i
only
. In
this case, x(M) appears in line 2 in the product x(S
j
only
)g
i
, and the coecient for x(M)
is (1)
C
where
C = d
i

_

S
ij

S
i
only

_
.
the electronic journal of combinatorics 19(2) (2012), #P1 7
In line 3, x(M) appears only in the product
_
lt
_
P(S
i
only
)
_
P(S
i
only
)
_
g
j
, and the coef-
cient for x(M) is (1)
C

where
C

S
i
only

S
i
only

+ d
j

_

S
ij

S
j
only

_
+ 2.
But using the identity from Eq. 1, and substituting for d
j
, we see
C

S
i
only

S
i
only

+
_

S
j
only

+ d
i

S
i
only

S
ij

S
j
only

_
+ 2
= d
i

S
i
only

S
ij

+ 2.
Thus, C is the same parity as C

, which implies that the coecient for x(M) in line 2,

and the coecient for x(M) in line 3 are the same.
The case where M = S
i
only
S
ij

S
j
only
and S
j
only
,= S
j
only
is the same. Thus, we
have shown that every monomial in line 2 either cancels, or appears in line 3 with the
same coecient.
We must now show that every monomial in line 3 either cancels, or appears in line 2
with the same coecient. Let x(M) be a monomial appearing in line 3. Either
M = S
j
only
S
ij

S
i
only
, or M = S
i
only
S
ij

S
j
only
.
We note that in each case, M contains a proper subset of S
j
only
or a proper subset of S
i
only
.
Additionally, the two cases when S
i
only
= S
i
only
, or S
j
only
= S
j
only
have already been
explicated above. Thus, in both cases, we have already shown that x(M) appears in line
2 with the same coecient.
We will now consider monomials of the form x(M) where M = S
j
only
S
ij

S
i
only
, and
show that these monomials cancel within line 3. The coecient for x(M) is (1)
C
(1)
D
where
C =

S
j
only

S
j
only

+ d
i

_

S
ij

S
i
only

_
, and
D =

S
i
only

S
i
only

+ d
j

_

S
ij

S
i
only

_
+ 2.
As before, using the identify from Eq. 1 and substituting for d
j
, we see C is the same
parity as D. Thus, (1)
C
(1)
D
= 0, and the monomial cancels.
Thus, we have shown that every monomial in line 2 either cancels within line 2, or
appears in line 3 with the same coecient, and vice versa. Additionally, we have not
utilized the properties of any particular monomial order to do so. Thus, we have shown
that g
1
, . . . , g
D
is a universal Gr obner basis for g
1
, . . . , g
D
.
The following corollary extends the theorem above to include boolean polynomials
of the form x
2
i
x
i
. This is particularly interesting because boolean polynomials are a
common ingredient in non-linear models of combinatorial problems.
Corollary 8. Let S
1
, . . . , S
D
with S
i
1, . . . , n (and [S
i
[ > 1) be a set that satises
the linear factor criterion. Let g
i
= P(S
i
), and let b
i
= x
2
i
x
i
. Then ( = b
1
, . . . , b
n

g
1
, . . . , g
D
is the universal Grobner basis for b
1
, . . . , b
n
+g
1
, . . . , g
D
.
the electronic journal of combinatorics 19(2) (2012), #P1 8
We observe that x
i
1 and x
2
i
x
i
are redundant equations, which explains the extra
condition [S
i
[ > 1, i.
Proof. By Theorem 6, we have already seen that g
1
, . . . , g
D
is a universal Gr obner basis.
Therefore, in order to show that ( satises Buchbergers criterion, it remains to show that
S(b
i
, b
j
)
G
= S(b
i
, g
j
)
G
= 0, without relying on properties of a particular monomial order,.
Because monomial orders are by denition well-orders, lt(b
i
) is always x
2
i
, and lt(g
i
)
is always x(S
i
), regardless of the specic monomial order.
We will rst show that S(b
i
, b
j
)
G
= 0 for i ,= j. Note that
S(b
i
, b
j
) =
x
2
i
x
2
j
x
2
i
(x
2
i
x
i
)
x
2
i
x
2
j
x
2
j
(x
2
j
x
j
) = x
2
i
x
j
x
i
x
2
j
= x
j
(x
2
i
x
i
) x
i
(x
2
j
x
j
).
Since [S
i
[ > 1, the coecients x
i
and x
j
are not divisible by lt(g
k
), k. Thus,
S(b
i
, b
j
)
G
= 0.
We will now show that S(b
i
, g
j
)
G
= 0, for all i, j pairs.
Case 1: Choose an i such that i / S
j
, and write g
j
:= x(S
j
) + P
rest
. Note
S(b
i
, g
j
) =
x
2
i
x(S
j
)
x
2
i
(x
2
i
x
i
)
x
2
i
x(S
j
)
x(S
j
)
(x(S
j
) + P
rest
) = x
i
x(S
j
) x
2
i
(P
rest
)
= x
i
(x(S
j
) + P
rest
) P
rest
(x
2
i
x
i
) = x
i
g
j
P
rest
(x
2
i
x
i
).
By the linear factor criterion, lt(P
rest
) is not divisible by lt(g
k
) for any k. Thus,
S(b
i
, g
j
)
G
= 0.
Case 2: Choose an i such that i S
j
, and write g
j
:= x(S
j
) x(S
j
i) + P
rest
.
Since i S
j
, this implies that lcm
_
lt(b
i
), lt(g
j
)
_
= x
i
x(S
j
) = x
2
i
x(S
j
i). Then
S(b
i
, g
j
) =
x
2
i
x(S
j
i)
x
2
i
(x
2
i
x
i
)
x
i
x(S
j
)
x(S
j
)
_
x(S
j
) x(S
j
i) + P
rest
_
= x
i
P
rest
(4)
=
_
x(S
j
i) P(S
j
i)
_
(x
2
i
x
i
), (5)
and S(b
i
, g
j
)
G
= 0 by the linear factor criterion. The equality of lines 4 and 5 can be
seen as follows. The polynomial x(S
j
i) P(S
j
i) is the polynomial P(S
j
i) with
the signs changed and the leading term removed. When multiplied by a positive
x
2
i
and a negative x
i
, every monomial appearing in the product also appears in
x
i
(P
rest
). To see this clearly, consider a monomial x(M) where M is a proper
subset of S
j
(this is the only kind of monomial appearing in P
rest
on line 4). There
are two cases:
Case 2a: i M. When x(M) is multiplied by x
i
(line 4), the sign of
the leading coecient changes, and the degree increases by one. In other
the electronic journal of combinatorics 19(2) (2012), #P1 9
words, x
i
x(M) appears in expanded product x
i
(P
rest
) with leading coecient
(1) (1)
d
j
|M|
. However, x(M i) appears in P(S
j
i) with the same parity
sign as x(M) in P
rest
(i.e., (1)
(d
j
1)(|M|1)
). Thus, the product P(S
j
i)(x
2
i
)
produces the same monomial with the same leading coecient as x
i
(P
rest
)
(line 5) and equality between lines 4 and 5 is preserved.
Case 2b: i / M. In this case, x(M) appears in P(S
j
i), but with opposite
sign as x(M) in P
rest
. In particular, x(M) in P
rest
has coecient (1)
d
j
|M|
as
before, but x(M) in P(S
j
i) has coecient (1)
(d
j
1)|M|
. Thus, the product
P(S
j
i)(x
i
) produces the same monomial with the same leading coecient
as x
i
(P
rest
) and equality between lines 4 and 5 is preserved
In cases 2a and 2b, we demonstrated that the monomials produced by P(S
j
i)(x
2
i
)
and P(S
j
i)(x
i
) respectively, appear in line 4. Thus, we have accounted for
every monomial in line 5, and we have shown that line 4 is equal to line 5.
We have shown that S(b
i
, b
j
)
G
= 0 for i ,= j, and that S(b
i
, g
j
)
G
= 0, for all i, j pairs,
without relying on any properties of a monomial order. Since we have already shown
that g
1
, . . . , g
D
is a universal Gr obner basis, this means that we have shown that
b
1
, . . . , b
n
g
1
, . . . , g
D
is a universal Grobner basis of b
1
, . . . , b
n
+g
1
, . . . , g
D
. This
concludes our proof.
In Section 4.3, we will represent the dominating set problem as a system of polyno-
mial equations in such a way that the representation is already a universal basis. This
representation follows the work of De Loera [21], where the graph coloring problem is
also represented in such a way that it is a universal Grobner basis. These kinds of repre-
sentations may prove useful in the context of combinatorial ideal membership questions,
and also with the advance of algorithms specically tailored for nding universal Grobner
basis, such as [4].
4 Dominating Sets, Ideals and Gr obner Bases
In this section, we begin by formulating the dominating set problem as a system of
polynomial equations. We extend this formulation to include a dominating set in a graph
G, a dominating set in a graph H, and a dominating set in the product graph GH.
We refer to this formulation (linking graphs G, H, and GH) in Section 5 during the
algebraic formulation of Vizings conjecture. In Section 4.2, we introduce the idea of a k-
domination cover or a k-cover. We explain the relation between k-covers and domination-
critical graphs, and provide various examples of k-covers. We also prove several properties
of k-covers, and provide a conjecture for future work. We unify these ideas in Section
4.3 by showing that k-covers provide the combinatorial interpretation of the universal
Gr obner basis of the ideals described in Section 4.1. Thus, the purpose of this section
is to explore two dierent non-linear models of the dominating set problem based on
two dierent combinatorial properties, and surprisingly, the second representation is the
universal Gr obner basis of the rst.
the electronic journal of combinatorics 19(2) (2012), #P1 10
4.1 Dominating Sets and Systems of Polynomial Equations
Let S
n
k
represent the set of k-subsets of 1, 2, . . . , n. Thus, [S
n
k
[ =
_
n
k
_
, and S S
n
k
implies that S 1, 2, . . . , n is a particular subset with [S[ = k. In the following system
of polynomial equations, there is one binary decision variable for every possible edge in a
graph with n vertices. Thus, the variable e
ij
is 1 if the edge between vertex i and vertex
j exists in the graph, and 0 otherwise. Since our graphs are undirected, we implicitly
assume the substitution e
ji
= e
ij
whenever j > i.
Theorem 9. There is a bijection between the set of solutions of the following system of
equations and the set of labeled graphs G in n vertices with a dominating set of size k.
e
2
ij
e
ij
= 0, for 1 i < j n,

SS
n
k
_

i / S
_

jS
(e
ij
1)
__
= 0. (6)
Example 10. Let n = 3 and k = 1. The variables in the system of polynomial equations
dened by Theorem 9 are e
12
, e
13
and e
23
. Furthermore, S
3
1
=
_
1, 2, 3
_
.
For the second equation, we have:
_
(e
21
1) + (e
31
1)
__
(e
12
1) + (e
32
1)
__
(e
13
1) + (e
23
1)
_
= 0.
However, as noted above, since the graph is undirected, we implicitly assume the substi-
tution e
21
= e
12
, e
31
= e
13
and e
32
= e
23
. Thus, the system of equations is as follows:
e
2
12
e
12
= 0, e
2
13
e
13
= 0, e
2
23
e
23
= 0
_
(e
12
1) + (e
13
1)
__
(e
12
1) + (e
23
1)
__
(e
13
1) + (e
23
1)
_
= 0.
The solutions to the system of equations are in bijection with the labeled graphs on three
vertices with a dominating set of size one:

Proof. We refer to the system of polynomial equations dened by Theorem 9 as through-

out this proof. We will dene a map between the solutions of and the labeled graphs
G in n vertices with a dominating set of size k, and show that is a bijection between
the two sets.
To deal with the problem of graph isomorphisms, we consider a set of n vertices with
a xed labeling 1 through n. Thus, two graphs G and G

on this labeled set of n vertices

are equal if and only if (i, j) E(G) implies that (i, j) E(G

). In other words, if G
and G

are isomorphic, they are not necessarily equal under this denition. Then, our
map simply takes a solution to , and converts it to a graph G on the labeled set of n
the electronic journal of combinatorics 19(2) (2012), #P1 11
vertices by adding the edges (i, j) to E(G) if and only if the variable e
ij
= 1. Then, is
one-to-one, since given any two solutions s and s

, if G = (s) = (s

) = G

, then clearly
s = s

.
We will now show that the image of is a subset of the set of labeled graphs G with
a dominating set of size k. The boolean equations e
2
ij
e
ij
= 0 force every variable e
ij
to
be zero or one; thus, the boolean equations turn edges on or o when applying the
map , and every solution corresponds to a particular graph G. We must now show that
since the solution satises Eq. 6, the particular graph G formed from the solution has a
dominating set of size k. Let A and B denote dierent pieces of Eq. 6 as follows.

SS
n
k
_

i / S
_

jS
(e
ij
1)
_
. .
A
_
. .
B
= 0.
The equation is only satised if one of the inner summations B (corresponding to some
set S) is zero. The value of an individual summand A in B is either zero or 1. However,
two dierent summands A, A

in the summation B can never mutually cancel, since if

they are both non-zero, they are both 1
|S|
. Thus, they are either both 1 or both +1.
Therefore, a summation B is only zero if every individual summand A is also zero, and A
is only zero if at least one edge variable has value one. Therefore, every i / S is adjacent
to a j S. In other words, G has a dominating set of size k.
Having shown that the image of is a subset of the set of labeled graphs G with a
dominating set of size k, we must now show that is onto, or that given any graph G
with a dominating set of size k,
1
(G) is a solution to . The map
1
(G) would be
applied as follows: if the edge e
ij
is present in G, turn it on by setting the variable
e
ij
= 1. If the edge e
ij
is not present in G, turn the variable e
ij
o by setting the
variable e
ij
= 0. Clearly, the boolean equations e
2
ij
e
ij
= 0 are satised. Since the
graph G has a dominating set of size k, let S = i
1
, . . . , i
k
be such a dominating set.
Thus, every vertex i not in the dominating set S must be adjacent to a vertex j that is
in the dominating set S. In other words, an edge e
ij
is on from i / S to j S, and
the (e
ij
1) term in the product corresponding to the dominating set S is equal to zero.
Since every vertex i / S must satisfy this condition, this implies that every summand in
the summation (corresponding to the dominating set S)

i / S
_

jS
(e
ij
1)
_
is equal to zero, and thus the entire summation is equal to zero. Since Eq. 6 is a product
of summations, the equation is satised.
Thus, is one-to-one and onto, and is a bijection between solutions of and the set
of labeled graphs G with a dominating set of size k.
We will now use the system of polynomial equations dened in Theorem 9 as a building
block to model dominating sets in G, H and GH.
the electronic journal of combinatorics 19(2) (2012), #P1 12
Theorem 11. There is a bijection between the set of solutions of the following system of
polynomial equations and the set of labeled graphs G, H in n, n

vertices with dominating

sets of size k, l respectively such that their Cartesian product graph GH has a dominat-
ing set of size r.
Representing a graph G in n vertices with a dominating set of size k:
e
2
ij
e
ij
= 0, for 1 i < j n,

SS
n
k
_

i / S
_

jS
(e
ij
1)
_
_
. .
P
k
G
= 0. (P
k
G
)
Representing the graph H in n

vertices with a dominating set of size l:

e

2
ij
e

ij
= 0, for 1 i < j n

SS
n

l
_

i / S
_

jS
(e

ij
1)
_
_
. .
P
l
H
= 0. (P
l
H
)
Representing the Cartesian product graph GH with a dominating set of size r:

SS
nn

r
_

gh/ S
_

g

hS
(e
gg
1)

gh

S
(e

hh
1)
_
_
. .
P
r
GH
= 0. (P
r
GH
)
Proof. It is clear from Theorem 9 that there is a bijection between the solutions of the
equations representing graphs G and H and the set of graphs in n, n

vertices with domi-

nating sets of size k, l respectively. The equation representing GH is of the same form,
except that this equation takes into account the unique structure of the product graph.
For example, if a vertex not in S is adjacent to a vertex in S, the adjacency is either due
to an edge in G, or an edge in H. In particular, gh / S is either adjacent to a vertex
g

h S if the edge (g, g

) is on in G, or gh / S is adjacent to a vertex gh

S if the
edge (h, h

) is on in H. Thus, the proof of the bijection follows the logic of the proof of
Theorem 9.
Since the system of polynomial equations described in Theorem 11 depends on the
variables n, k, n

, l and r, we dene the ideal I(n, k, n

, l, r) as
I(n, k, n

, l, r) := P
k
G
, P
l
H
, P
r
GH
, e
2
e,
where e
2
e denotes the entire set of boolean edge equations
e
2
ij
e
ij
: 1 i < j n, e

2
ij
e

ij
: 1 i < j n

, .
the electronic journal of combinatorics 19(2) (2012), #P1 13
We note that I(n, k, n

, l, r) is radical by Lemma 2, since the boolean equations e

2
e
are univariate and square-free. We now dene k-covers, which provide a combinatorial
interpretation of the universal Gr obner basis of I(n, k, n

, l, r) in Section 4.3. We note that

what is important about the next section is not the uniqueness or complexity of the de-
nition of k-covers, but rather the interesting relationship between the ideal I(n, k, n

, l, r),
the combinatorial idea of a k-cover, and the universal Grobner basis of the ideal.
4.2 k-Covers and k-Dominating Sets
We begin by recalling that a graph G is domination-critical if, for any two non-adjacent
vertices u, v, the graph G

:= G+(u, v) has (G

) = (G)1. In other words, a graph G is

domination-critical if, whenever any edge is added to G, the domination number decreases
by one. Thus, k-domination-critical graphs are created from k-dominating graphs by
adding edges. In this section, we study the complements of domination-critical graphs.
We dene a k-domination-cover (or k-cover) as analogous to a k-dominating graph, and
a minimal k-cover as analogous to a k-domination-critical graph. Just as a domination-
critical graph is obtained from a k-dominating graph by adding edges, a minimal k-cover
is obtained from a k-cover by removing edges.
Before we begin, we recall a few denitions. Let K
n
denote the complete graph in n
vertices (an n-clique). For S V (G), the open neighborhood of S (denoted by N
G
(S), or
simply N(S) when the context of the graph is clear) is dened to be
N
G
(S) := v : (u, v) E(G) and u S and v / S.
The common neighborhood of S V (G) (denoted by cmN
G
(S), or simply cmN(S) when
the context of the graph is clear) is dened to be
cmN
G
(S) :=

uS
N
G
(u).
Example 12. In the following example, let S = 0, 1, 3. Then cmN(S) = 6.
Denition 13. A graph C is a k-cover if cmN
C
(S) ,= for all S V (C) with [S[ = k1.
We say that a graph C is a k-cover if every set of size k 1 has a common neighbor.
We note that k-covers are only dened for k 2.
Denition 14. A k-cover C is minimal if for all e E(C), C

:= C e is not a k-cover.
the electronic journal of combinatorics 19(2) (2012), #P1 14
Example 15. Here we see a minimal 3-cover (left) and its complement (right).
We refer to graphs of the type described by Denition 13 as k-covers, because we
are taking n vertices and then covering those n vertices with k-cliques such that the
k-cliques intersect in a very particular way. Notice that the 3-cover illustrated in Ex. 15
takes six vertices, and then covers those six vertices with triangles such that any subset
of size two has a common neighbor.
Proposition 16. Given a k-cover C, every v V (C) appears in a clique of size k.
Proof. Since every set of size k 1 in V (C) has a common neighbor, every vertex has at
least one outgoing edge. Thus, for any v
1
V (C), v
1
is adjacent to some v
2
. If 2 k 1,
both v
1
and v
2
are each adjacent to a third vertex v
3
. In other words, v
1
, v
2
and v
3
form a
3-clique. By repeating this process k 1 times, we form a k-clique containing v
1
. Since v
1
was an arbitrary starting point, this algorithm can be repeated for any vertex, and every
v V (C) appears in a clique of size k.
We also observe that while 2-covers can be disconnected, k-covers with k 3 are
connected. Additionally, since the diameter of a graph is the longest shortest path between
any two vertices, and every two vertices has a common neighbor, k-covers with k 3 have
diameter at most two.
Proposition 17. A graph G is k-domination-critical if and only if G is a minimal k-
cover.
Proof. If G is k-domination-critical, then G has a dominating set of size k, but no dom-
inating set of size k 1. Thus, every (k 1)-subset of vertices in G has a common
neighbor, and G is a k-cover. Furthermore, since G is k-domination-critical, for any two
non-adjacent vertices u, v,
_
G + (u, v)
_
= k 1. In other words, if any edge (u, v) is
removed from G, then there is at least one (k 1)-subset of vertices that no longer has a
common neighbor. Thus, G is a minimal k-cover.
Conversely, assume that G is a minimal k-cover. Then, for all e E(G), Ge is not
a k-cover. This implies that there is some set D V (G) of size k 1 that does not have
a common neighbor. In other words, for all v
_
V (G) D
_
, v is not adjacent to some
vertex in D. In other words, D is a dominating set of size k 1 in G. Thus, we have
shown that when any edge is added to G (or removed from G), there is a dominating set
of size k 1 in G. Thus, in order to prove that G is k-domination-critical, it remains to
show that there exists a dominating set of size k in G, and that there does not exist a
dominating set of size k 1 in G.
the electronic journal of combinatorics 19(2) (2012), #P1 15
Clearly, there is no dominating set of size k 1 in G, since G is a k-cover. We will now
show that G contains a dominating set of size k. Consider any two non-adjacent vertices
u, v V (G). Without loss of generality, let D = i
1
, . . . , i
k2
, u be the dominating set
of size k 1 in G+(u, v). Since D is a dominating set in G+(u, v), but not a dominating
set in G, the only vertex that D does not dominate in G is v. Thus, D+v is a dominating
set in G, and since [D + v[ = k, G is k-domination-critical.
We note that in [32], Sumner and Blitch extensively explore properties of 3-domination-
critical graphs. They explicitly categorize 2-domination-critical graphs as follows:
Theorem 18 (Sumner and Blitch, 1983). A graph G is 2-domination-critical if and only
if G =
n
i=1
K
1,n
i
with n 1.
The Sumner-Blitch categorization of 2-domination-critical graphs is equivalent to Def-
inition 13, since for any 2-cover, every vertex is adjacent to at least one other vertex.
Example 19. Here we see a 2-cover on 16 vertices. We note that this 2-cover is the union
of two K
1,3
graphs, two K
1,2
graphs, and a K
1,1
graph. Additionally, every single vertex
(every set S with [S[ = 1) has a common neighbor.
Our categorization is an extension of the Sumner-Blitch categorization since Denition
13 is generalized for the complements of k-dominating graphs, although further charac-
terizations are needed for minimal k-covers. We now link minimal k + 1-covers with
k-dominating graphs.
Theorem 20. A graph G = (V, E) has a dominating set of size k if and only if for all
minimal k + 1-covers C = (V, E
cov
), E(G) E
cov
,= .
Via this theorem, we characterize graphs with dominating sets of size one in terms
of 2-covers. Since one is the smallest dominating set, this explains why we only dene
k-covers for k 2.
Proof. Assume G = (V, E) has a dominating set D V (G) of size k. Consider any
minimal k + 1-cover C = (V, E
cov
). Since D is also a subset of V (C), and since [D[ = k,
by Denition 13, D has a common neighbor v in C. Thus, for every u D, (u, v) E
cov
.
Since D is a dominating set in G and v / D, there must exist an edge (u, v) E(G) with
u D. Since (u, v) E(G) and (u, v) E
cov
, E(G) E
cov
,= .
Conversely, assume that for all minimal k + 1-covers C = (V, E
cov
), E(G) E
cov
,= .
We must show that G contains a dominating set of size k. We proceed by contradiction.
Assume that G does not contain a dominating set of size k, and form a new graph
G
crit
by adding edges to G until the resulting graph is k + 1-domination-critical. Thus,
E(G) E(G
crit
), and G
crit
has a dominating set of size k + 1, but no dominating set of
size k.
the electronic journal of combinatorics 19(2) (2012), #P1 16
Next, we consider the complement of G
crit
(denoted by G
crit
). Since G
crit
is k + 1-
critical, G
crit
is a minimal k + 1-cover by Proposition 17. We note that E(G
crit
) E(G),
and E(G
crit
) E(G
crit
) = . However, E(G) E(G
crit
). Therefore, E(G
crit
) E(G) = .
But this is a contradiction, since G
crit
is a minimal k +1-cover, and E(G) E
cov
,= , for
all minimal k + 1-covers C = (V, E
cov
). Thus, G contains a dominating set of size k.
We note that, according to Thm. 20, in order to demonstrate that a graph G does not
have dominating set of size k, it is sucient to produce a k +1-cover C that is a subgraph
of G. This k + 1-cover then becomes a certicate of the non-existence of a k-dominating
set: it is a coNP certicate. However, even though the cover itself is polynomial-size in
[G[, there are no known polynomial-time algorithms for verifying that every k-subset of
C has a common neighbor. Therefore, there is no conict between the use of k-covers as
certicates, and the conjectured non-equality of NP and coNP.
We now explore properties of k-covers.
Theorem 21. A graph C is a k-cover if and only if, for all S V (C) with 1 [S[ k1,
there exists a clique Q in cmN
C
(S) such that [Q[ = k[S[. Moreover, every v cmN
C
(S)
appears in a clique Q of size k [S[.
Proof. Assume that a graph C is a k-cover. Given S V (C), if [S[ = k 1, we know by
denition of a k-cover that cmN(S) is non-empty. Therefore, a clique Q of size one exists
in cmN(S), and moreover, all vertices in cmN(S) trivially form cliques of size one.
Now consider S V (C) with 1 [S[ k 2. As before, by denition, since
[S[ < k 1, cmN(S) is non-empty. Let v
1
cmN(S). Since [S v
1
[ k 1, the set
S v
1
has a common neighbor v
2
. Thus, the set v
1
, v
2
forms a clique of size two in
cmN(S). If [S v
1
v
2
[ k 1, we repeat this operation, and we note that the set
S v
1
v
2
has a common neighbor v
3
, and that v
1
, v
2
, v
3
forms a clique of size three
in cmN(S). We repeat this operation exactly k [S[ 1 times until we have formed the
k [S[-clique Q = v
1
, v
2
, . . . , v
k|S|
in cmN(S).
Therefore, for all 1 [S[ k 1, there exists a clique Q in cmN(S) such that
[Q[ = k [S[. Moreover, every v cmN(S) appears in a clique Q of size k [S[, since
this operation can be repeated with reference to any vertex v.
Conversely, let C be a graph such that for all S V (C) with 1 [S[ k 1, there
exists a clique Q in cmN(S) such that [Q[ = k [S[. In particular, let S be a subset of
V (C) with [S[ = k 1. Then, there exists a clique Q of size one in cmN(S). Therefore,
by denition, C is a k-cover.
We have already shown that every vertex in a k-cover appears in a k-clique, but we
have not discussed how these k-cliques intersect. We present the following conjecture.
Conjecture 22. A graph C is a k-cover if and only if for all S V (C) with [S[ = k 1,
there exists a map q from v S to k-cliques in C such that for any u, v S, [q(u)q(v)[
k 2.
Example 23. Here is an example of Conjecture 22 on a 3-cover of 7 vertices.
the electronic journal of combinatorics 19(2) (2012), #P1 17
Consider S = c, g. Then, if q(c) = c, d, f and q(g) = a, f, g, [q(c) q(g)[ = [f[ =
1 = k 2. Additionally, consider S = e, g. Then, if q(e) = b, d, e and q(g) = a, b, g,
[q(e) q(g)[ = [b[ = 1 = k 2. Upon inspection, we can see that given any set S with
[S[ = k 1 = 2, a similar map q can be constructed and the conjecture holds.
4.3 k-Covers, k-Dominating Sets and a Universal Gr obner Basis
of I(n, k, n
/
, l, r)
In Section 4.1, we outlined a representation of the k-dominating set problem as a system of
polynomial equations, and dened the ideal I(n, k, n

, l, r). In Theorem 9, I(n, k, n

, l, r)
was dened by three, high-degree polynomials P
k
G
, P
l
H
and P
r
GH
, and their associated
boolean edge equations. Each of these polynomials was a series of products, with each
product a sum of products. Thus, the polynomials P
k
G
, P
l
H
and P
r
GH
were a brute-force
enumeration of every possible vertex set of size k, dominating or otherwise, in the graph.
In this section, we present another representation of the ideal I(n, k, n

, l, r). This
representation is based on k + 1-covers, with each polynomial equation corresponding
to a minimal k + 1-cover of V (G). Thus, I(n, k, n

, l, r) can also be generated by many

dierent polynomials of comparatively low degree, as opposed to only three polynomials
of high degree. However, there is currently no known algorithm for enumerating minimal
k +1-covers, which is equivalent to the problem of enumerating k +1-domination-critical
graphs. Thus, another point of comparison between the representation expressed here
and Theorem 9 is that the polynomials described in Theorem 9 can be explicitly written
down, whereas polynomials based on k + 1-covers, while combinatorially explicit, may
be dicult to write down explicitly enough for the purpose of computation. However,
the potential advantage of the cover representation is that k + 1-covers are collections of
edges that satisfy the linear factor criterion (Denition 5). Therefore, by Theorem 6 and
Corollary 8, the representation described below is a universal Grobner basis.
In presenting a combinatorial interpretation of any Gr obner basis, we must be partic-
ularly careful of input instances where the system of polynomial equations is infeasible.
In these cases, the associated variety is empty and the associated ideal is the entire ring.
This implies that the universal Gr obner basis is simply the number one. In our case, we
will exclude input instances where the system of polynomial equations is infeasible by
restricting the values of n, n

, k and l. However, in Theorem 38, we will show that the

instances lost by this restriction correspond exactly to instances where Vizings conjecture
is known to be true.
Before we begin, we introduce some notation. Let C
n
k+1
be the set of all minimal
k + 1-covers on n vertices. For C C
n
k+1
, let
P(C) :=

eE(C)
(e 1).
the electronic journal of combinatorics 19(2) (2012), #P1 18
Theorem 24. There is a bijection between the solutions of the following system of equa-
tions and the labeled graphs G in n vertices with a dominating set of size k.
e
2
ij
e
ij
= 0, for 1 i < j n,
P(C) = 0, for each C C
n
k+1
. (7)
We note that if k = n, there are no n + 1 covers on n vertices. Thus, C
n
n+1
= , and
the only equations that appear are of the form e
2
e = 0. Thus, any graph is a solution
to this system, which is reasonable since every graph has a dominating set of size n.
Proof. As in the proof of Theorem 9, we must dene a map and show that provides a
bijection between the set of solutions and the set of graphs with a dominating set of size
k. We will use the same map dened in the proof of Theorem 9, and thus, we already
know that the map is one-to-one, and we only need show that the image of is the set of
graphs with a dominating set of size k, and that the map is onto.
To consider the image of the map , we note that, as in Theorem 9, every solution
corresponds to a particular graph G (the assignment of the variables e
ij
to zero or one
simply turns the edges on or o in G). Since the cover equations (Eqs. 7) are satised,
this implies that for all minimal k + 1-covers, E(G) E(C) ,= . Then, by Theorem 20,
G has a dominating set of size k.
To show that is onto, consider a graph G in n vertices that has a dominating set of
size k. As before, we must show that
1
(G) (dened by setting variables e
ij
to zero or
one, depending on whether or not e
ij
E(G)) maps to a solution. Clearly, the boolean
equations e
2
ij
e
ij
= 0 are satised. Since the graph G has a dominating set of size k, for
any minimal k + 1-cover C, E(G) E(C) ,= by Theorem 20. Therefore, at least one
edge in every cover is on and the cover equations (Eqs. 7) are satised.
Let I(n, k) denote the ideal generated by polynomials described in Theorem 24. We
will now prove that this representation is a universal Gr obner basis. We note that we dis-
covered the connection between covers and Gr obner bases by experimental investigations
using CoCoA Lib [1].
Corollary 25. The basis I(n, k) described in Theorem 24 is a universal Grobner basis.
Proof. We must show that P(C) : C C
n
k+1
satises the linear factor criterion (Def.
5). Let C
i
, C
j
, C
k
be covers in C
n
k+1
. Since each are minimal covers, it is clear that C
k
can
never be a proper subset of C
i
C
i
C
j
or C
i
C
i
C
j
. From Thm. 6 and Cor. 8, we
can see that the basis of I(n, k) described in Thm. 24 is a universal Grobner basis.
In Section 4.1, we used the system of polynomial equations dened in Theorem 9 to
model the larger question of dominating sets in graphs G, H and GH (Theorem 11). We
will repeat the process here, using the cover-based model from Theorem 24 as a building
block. However, a system of polynomial equations based on k+1-covers is also intrinsically
based on graph intersections. Thus, we must dene the edge variables that appear in the
intersection of an arbitrary r-cover on nn

vertices and an arbitrary product graph.

the electronic journal of combinatorics 19(2) (2012), #P1 19
Denition 26. Given graphs G and H, let C be a graph on the vertices V (G) V (H).
Then the set

C
_
E(G) E(H)
_
is dened to be the following set of edges:

C =
_
(g, g

) : (gh, g

h) E(C)
_

_
(h, h

) : (gh, gh

) E(C)
_
.
Now we present the cover-based model that links dominating sets in G, H and GH.
As before, this system of polynomial equations will be used in the algebraic representation
of Vizings conjecture in Section 5, and the restriction on the values of n, k, n

, l and r will
be more meaningful in that context.
Theorem 27. Let n, k, n

, l and r be integers such that r min(n, n

). There is a
bijection between the set of solutions of the following system of polynomial equations and
the set of labeled graphs G, H in n, n

vertices with dominating sets of size k, l respectively

such that their Cartesian product graph GH has a dominating set of size r.
Representing a graph G in n vertices with a dominating set of size k:
e
2
ij
e
ij
= 0, for 1 i < j n,
P(C) = 0, for each C C
n
k+1
.
Representing the graph H in n

vertices with a dominating set of size l:

e

2
ij
e

ij
= 0, for 1 i < j n

,
P(C) = 0, for each C C
n

l+1
.
Representing the Cartesian product graph GH with a dominating set of size r:
P
_

C
_
= 0, for each C C
nn

r+1
.
Proof. It is clear from Theorem 24 that there is a bijection between the solutions of the
equations representing graphs G and H and the set of labeled graphs in n, n

vertices with
dominating sets of size k, l respectively. The equation representing GH is of the same
form, except that it takes into account the unique structure of the product graph.
Assume that GH has a dominating set D V (GH) of size r. We will show that
the cover equations associated with GH are satised. Let C
nn

r+1
be a minimal r +1-cover
on V (GH). Since C
nn

r+1
is an r + 1-cover, every subset of size r has a common neighbor
in V (C
nn

r+1
) = V (GH). In particular, D has a common neighbor gh V (C
nn

r+1
). Since
D is a dominating set of GH and gh is not in D, the vertex gh must be dominated
by a vertex in D. Therefore, either gh

D with (h, h

) E(H), or g

h D with
(g, g

) E(G). In rst case, the edge (gh

, gh) E(C
nn

r+1
) E(GH), and in the second
case, the edge (g

h, gh) E(C
nn

r+1
) E(GH). In either case, E(C
nn

r+1
) E(GH) ,= ,
and each of the cover equations associated with GH are satised.
Conversely, assume that each of the cover equations associated with GH are satised.
We must show that GH has a dominating set of size r. We proceed by contradiction.
the electronic journal of combinatorics 19(2) (2012), #P1 20
Assume that GH does not have a dominating set of size r, and consider the complement
of GH (denoted by GH).
Since GH does not contain a dominating set of size r, every subset of size r in
V (GH) has a common neighbor. Thus, by Denition 13, GH is a r + 1-cover. Fur-
thermore, E(GH)E(GH) = . We remove edges from GH until we nd a subgraph
C that is a minimal r + 1-cover. Since C is a subgraph of GH, E(GH) E(C) = .
However, edges in C of the form (gh, g

) where g ,= g

and h ,= h

do not correspond to
variables in our system of polynomial equations, and thus, we have not yet shown that
the set

C is non-empty and the equation P(

C) = 0 is not satised. We must show

that C contains at least one edge of the form (gh, g

h) or (gh, gh

).
By assumption, r min(n, n

). Without loss of generality, let n

n and let S
V (C) = V (GH) be a subset of size r such that g : gh S = V (G). In other
words, choose S such that there is at least one vertex in S per G-level. Since C is
an r + 1-cover, S has a common neighbor gh V (C), and since gh is connected to
every vertex in S and there is at least one vertex per G-level in S, there exists a vertex
gh

S. Thus, (gh, gh

) E(C), implying the set

C is non-empty. But recall that

E(GH) E(C) = , which implies that the equation P(C) = 0 is not satised. This
is a contradiction with our assumption that each of the cover equations associated with
minimal r + 1-covers are satised. Thus, GH contains a dominating set of size r.
The ideal described by Theorem 27 is the set of polynomials vanishing on graphs G, H
with dominating sets k, l respectively, such that GH has a dominating set of size r.
Thus, the ideal described by Theorem 27 is the same as the ideal described by Theorem
11: both are I(n, k, n

, l, r). However, the question of whether the basis described by

Theorem 11 is a universal Grobner basis is not immediately resolvable. Given two r + 1-
covers C and C

on nn

vertices, it does seem possible that for large values of r and smaller
values of k and l, a k + 1-cover on n vertices (or an l + 1-cover on n

vertices) might be
a proper subgraph of C C

. In such a scenario, the collection of linear factors would

not satisfy the linear factor criterion described by Denition 5, and the basis would not
be a universal Grobner basis. The natural question to then pose is the following: for
what values of r is the cover representation of I(n, k, n

, l, r) a universal Grobner basis?

In Section 5, we will show that this question is equivalent to Vizings conjecture.
5 An Algebraic Formulation of Vizings Conjecture
We now express Vizings conjecture in terms of the ideals described in Section 4. By
dening two particular zero-dimensional, radical ideals and then intersecting them, we
transform Vizings conjecture from a question about dominating sets and product graphs
to an ideal membership question involving the product of two polynomials. This algebraic
representation suggests a variety of computational approaches, from large-scale, sparse
linear algebra computations such as those demonstrated in [24, 23, 26] to Gr obner basis
calculations customized for the linear factor criterion (Def. 5). Although Gr obner basis
computations and the ideal membership question itself are both known to be EXPSPACE-
the electronic journal of combinatorics 19(2) (2012), #P1 21
complete [16], algebraic algorithms customized for specic NP-complete combinatorial
properties (such as graph 3-colorability) have yielded surprisingly practical computation
approaches on some large examples [23]. However, renements to known algorithms
based on the algebraic and combinatorial properties of these particular dominating set
representations have not yet been explored. We leave this question for future work.
After describing the algebraic representation of Vizings conjecture, we transfer the
ideal membership question involving the product of two cover polynomials back to the
realm of graph theory. This transformation yields a conjecture involving k-covers that is
the complement of Vizings conjecture. We conclude by reclaiming a known result with a
cover-based proof, and linking universal Gr obner bases to Vizings conjecture.
5.1 Ideals, Varieties and Vizings Conjecture
We begin by dening three dierent varieties, and then relating the vanishing ideals
associated with these varieties to the ideals described in Section 4. Each of the following
varieties are a set of points such that each point represents a pair of graphs G, H in n, n

vertices such that GH has a dominating set of size kl 1. Additionally,

1. Let V
k1
l
be a variety such that every point represents a pair of labeled graphs G, H
with dominating sets of size k 1, l respectively.
2. Let V
k
l1
be a variety such that every point represents a pair of labeled graphs G, H
with dominating sets of size k, l 1 respectively.
3. Let V
k
l
be a variety such that every point represents a pair of labeled graphs G, H
with dominating sets of size k, l respectively.
Throughout this section, graphs are always labeled graphs. We dene the following ideals.
I
k1
l
:= I(n, k l, n

, l, kl 1), I
k
l1
:= I(n, k, n

, l l, kl 1), I
k
l
:= I(n, k, n

, l, kl 1).
Notice that in each of these ideals, we have set r = kl 1. According to the denitions
of I(n, k, n

, l, r) given in Section 4, V
k
l
= V (I
k
l
), V
k1
l
= V (I
k1
l
) and V
k
l1
= V (I
k
l1
).
Recall that if a given ideal I is radical, then I(V (I)) = I. Since the ideals I
k
l
, I
k1
l
and
I
k
l1
are radical (by Lemma 2), regardless of whether we choose the representation of
I
k
l
from Section 4.1, or the representation of I
k
l
from Section 4.3, I
k
l
= I(V
k
l
), I
k1
l
=
I(V
k1
l
) and I
k
l1
= I(V
k
l1
). In the following lemmas, we will relate Vizings conjecture
to these ideals and varieties. It is important to note that the algebraic representation of
Vizings conjecture described below is independent of the internal representation of the
ideal I(n, k, n

, l, r). In other words, the following lemmas will hold for any representation
of I
k
l
, I
k1
l
and I
k
l1
as long as the ideals are radical, and I
k
l
= I(V
k
l
), I
k1
l
= I(V
k1
l
) and
I
k
l1
= I(V
k
l1
). Thus, if another representation of I(n, k, n

, l, r) is found in the future with

a diering set of computational or combinatorial properties, this formulation of Vizings
conjecture remains valid.
Lemma 28. V
k1
l
V
k
l1
= V
k
l
if and only if Vizings conjecture is true.
the electronic journal of combinatorics 19(2) (2012), #P1 22
Proof. Every point in V
k
l
corresponds to a graph G with (G) k and a graph H with
(H) l such that (GH) kl 1.
Assume that Vizings conjecture is true. Thus, (G)(H) (GH) for all graphs
G, H. In particular, if (G) = k and (H) = l, then kl (GH). In particular,
(GH) can never equal kl 1. Thus, if there is a pair of graphs G, H such that
(GH) kl 1, then either (G) k 1 or (H) l 1. Thus, any point appearing
in V
k
l
also appears in V
k1
l
V
k
l1
, and V
k1
l
V
k
l1
= V
k
l
.
Conversely, assume that V
k1
l
V
k
l1
= V
k
l
. Then, for every pair of graphs G, H such
that (GH) kl 1, then either (G) k 1 or (H) l 1. In other words, if
(G) = k and (H) = l, then (GH) > kl 1. This implies that (G)(H) (GH),
or that Vizings conjecture is true.
Lemma 29. I
k1
l
I
k
l1
= I
k
l
if and only if Vizings conjecture is true.
Proof. If I
k1
l
I
k
l1
= I
k
l
, then V
k1
l
V
k
l1
= V
k
l
(and vice versa). This can be seen via
the results in Section 2, since if I
k1
l
I
k
l1
= I
k
l
, then V (I
k1
l
I
k
l1
) = V (I
k1
l
)V (I
k
l1
) =
V
k1
l
V
k
l1
= V (I
k
l
) = V
k
l
. Thus, Vizings conjecture is true via Lemma 28.
We have now equated Vizings conjecture with a question about the equality of two
ideals. To prove this equality, we must prove the inclusion in both directions. The
inclusion in one direction is fairly easy to see; however, the inclusion in the other direction
remains open.
Lemma 30. V
k1
l
V
k
l1
V
k
l
.
Proof. Consider any point p in V
k1
l
V
k
l1
. This point either represents graphs G, H
with dominating sets k 1, l respectively, or graphs G, H with dominating sets k, l 1
respectively (in both cases, GH contains a dominating set of size kl 1). However, if G
contains a dominating set of size k 1 (or l 1), G also contains a dominating set of size
k (or size l). Therefore, any point representing graphs G, H with dominating sets k 1, l
respectively, or graphs G, H with dominating sets k, l 1 respectively also represents
graphs G, H with dominating sets k, l respectively. Thus, any point p V
k1
l
V
k
l1
is
also a point p V
k
l
.
Corollary 31. I
k
l
I
k1
l
I
k
l1
.
Proof. Since V
k1
l
V
k
l1
V
k
l
, this implies that I(V
k
l
) I
_
V
k1
l
V
k
l1
_
, which implies
that I
k
l
I
k1
l
I
k
l1
(see [11], Chapter 4).
Thus, in order to conclude a proof Vizings conjecture, we must show that I
k1
l
I
k
l1

I
k
l
. However, recall from the conclusion of Section 2, if the representations of I
k
l
, I
k1
l
and
I
k
l1
satisfy the conditions specied in Lemma 3, we can explicitly describe a basis for
I
k1
l
I
k
l1
:
I
k1
l
I
k
l1
=
_
I
k1
l
I
k
l1
=

fg : f I
k1
l
, g I
k
l1
_
+e
2
e.
the electronic journal of combinatorics 19(2) (2012), #P1 23
Thus far in this section, without specifying the representation for I
k
l
, etc., we have
shown that proving Vizings conjecture is equivalent to proving the equality of two ideals.
We will now show that for each of the representations specied in Section 4, proving the
opposite inclusion reduces to a problem in ideal membership, which implies, far more
signicantly, that proving Vizings conjecture reduces to a computational problem in
Gr obner bases or linear algebra.
Using the Representation from Theorem 11:
Let h be any polynomial in I
k1
l
I
k
l1
, where I
k1
l
and I
k
l1
are represented using the
polynomials dened by Theorem 9. Then h I
k1
l
I
k
l1
can be written as:
h = ()P
k1
G
P
k
G
+ ()P
k1
G
P
l1
H
+ ()P
k1
G
P
GH
+ ()P
k1
G
(e
2
e) + ()P
l
H
P
k
G
+ ()P
l
H
P
l1
H
+ ()P
l
H
P
GH
+ ()P
l
H
(e
2
e) + ()P
GH
P
k
G
+ ()P
GH
P
l1
H
+ ()P
GH
P
GH
+ ()P
GH
(e
2
e) + ()(e
2
e)P
k
G
+ ()(e
2
e)P
l1
H
+ ()(e
2
e)P
GH
+ ()(e
2
e)(e
2
e) + ()(e
2
e), (8)
where P
GH
is equal to P
kl1
GH
. We must show that h is also in I
k
l
. Specically, we must
show that there exists polynomial coecients such that
h = ()P
k
G
+ ()P
l
H
+ ()P
GH
+ ()(e
2
e). (9)
Comparing Eqs. 8 and 9, we see that the only term which is not already expressed in
terms of polynomials in I
k
l
is the product P
k1
G
P
l1
H
. Thus, we must nd an algebraic
relationship or a syzygy such that
P
k1
G
P
l1
H
= ()P
k
G
+ ()P
l
H
+ ()P
GH
+ ()(e
2
e). (10)
This is equivalent to asking whether or not P
k1
G
P
l1
H
I
k
l
. Here is the link between
Vizings conjecture and ideal membership: a conjecture about dominating sets in product
graphs is an ideal membership question about the product of two polynomials.
Lemma 32. P
k1
G
P
l1
H
I
k
l
if and only if Vizings conjecture is true.
Proof. If P
k1
G
P
l1
H
I
k
l
, then any polynomial h I
k1
l
I
k
l1
is also in I
k
l
. In other words,
I
k1
l
I
k
l1
I
k
l
. Lemma 30 and Corollary 31 establish the other direction of the inclusion,
and I
k1
l
I
k
l1
= I
k
l
. Thus, by Lemma 29, Vizings conjecture is true. Conversely, if
Vizings conjecture is true, then I
k1
l
I
k
l1
= I
k
l
, which implies that P
k1
G
P
l1
H
I
k
l
.
Unfortunately, performing these computations was quite dicult. We worked on ma-
chines with dual Opteron nodes, 2 GHz clock speed, and 12 GB of RAM. We used the
custom C
++
exact arithmetic linear algebra solver and the method described in [24], [23]
and [26]. We rst tested the smallest possible example of n = k = n

= l = 2. In order
to nd the syzygy dened by Eq. 10, we constructed a 100 84 linear system, solved in
under a second, yielding a syzygy of degree 6. However, when we tested the next largest
the electronic journal of combinatorics 19(2) (2012), #P1 24
example, with n = 3, k = n

= l = 2, we were unable to nd a syzygy, although we

determined that the syzygy had degree 8 or larger. The degree 7 linear algebra system
had size 158, 412 2, 310 and took 6,862 seconds ( 2 hours) to solve. However, the
degree 8 linear algebra system remained unsolved even after days of computation, most
likely due to the magnitude of the numbers involved. For example, one of the coecients
in P
k
G
was 2,106,048,060. It is easy to imagine the computationally intensive nature of
exact arithmetic on numbers of that order in a linear system with millions of rows and
columns. However, we again note that the specic combinatorial properties of these rep-
resentations have not yet been exploited. It is a question of future work to improve these
computations.
Using the Representation from Theorem 27:
In Lemma 32, we showed that proving Vizings conjecture using the representation de-
scribed by Theorem 11 was equivalent to proving that P
k1
G
P
l1
H
I
k
l
. We now show
that when the representation of I
k
l
corresponding to covers (Theorem 27) is used, Viz-
ings conjecture reduces to both an ideal membership question involving the product of
two cover polynomials, and a graph theoretic question that is the complement of Vizings
conjecture.
In the cover representation of I
k
l
, we denote the various cover polynomials as
P(C
n
k
), P(C
n

l
) and P
_

C
nn

kl
_
. As before, h I
k1
l
I
k
l1
can be written as follows:
h = ()P(C
n
k
)P(C
n
k+1
) + ()P(C
n
k
)P(C
n

l
) + ()P(C
n
k
)P
_

C
nn

kl
_
+ ()P(C
n
k
)(e
2
e)
+ ()P(C
n

l+1
)P(C
n
k+1
) + ()P(C
n

l+1
)P(C
n

l
) + ()P(C
n

l+1
)P
_

C
nn

kl
_
+ ()P(C
n

l+1
)(e
2
e)
+ ()P
_

C
nn

kl
_
P(C
n
k+1
) + ()P
_

C
nn

kl
_
P(C
n

l
) + ()P
_

C
nn

kl
_
P
_

C
nn

kl
_
+ ()P
_

C
nn

kl
_
(e
2
e) + ()(e
2
e)P(C
n
k+1
) + ()(e
2
e)P(C
n

l
)
+ ()(e
2
e)P
_

C
nn

kl
_
+ ()(e
2
e)(e
2
e) + ()(e
2
e). (11)
Again, to conclude the proof of Vizings conjecture, we must show that h I
k
l
. More
specically, we must show that there exist coecients such that
h = ()P(C
n
k+1
) + ()P(C
n

l+1
) + ()P
_

C
nn

kl
_
+ ()(e
2
e). (12)
Comparing Eqs. 11 and 12, we see that the only term which is not already expressed in
terms of polynomials in I
k
l
is the product P(C
n
k
)P(C
n

l
). Thus, we must nd an algebraic
relationship or a syzygy such that
P(C
n
k
)P(C
n

l
) = ()P(C
n
k+1
) + ()P(C
n

l+1
) + ()P
_

C
nn

kl
_
+ ()(e
2
e).
This is equivalent to asking whether or not P(C
n
k
)P(C
n

l
) I
k
l
. However, recall that the
cover representations are not just a basis, but a universal Grobner basis. Our experimental
investigations using CoCoA Lib [1] have indicated that that not only is P(C
n
k
)P(C
n

l
) I
k
l
,
but that there exists a P
_

C
nn

kl
_
such that P(C
n
k
)P(C
n

l
) = P
_

C
nn

kl
_
. In other words,
P(C
n
k
)P(C
n

l
) is itself an element of the Grobner basis of I
k
l
. We were not able to verify
the electronic journal of combinatorics 19(2) (2012), #P1 25
this conjecture on large examples because of the exponential number of monomials in
the expanded cover polynomials. For example, P(C
n
k
) may be compactly represented
as a product of L linear factors, but when P(C
n
k
) is expanded during the calculation of
the Grobner basis, 2
L
monomials are generated. Indeed, even very small examples often
took days of computation. We are interested in exploring modications to Gr obner basis
algorithms to exploit the factored form of these input bases for future work.
We will now prove several lemmas and extrapolate the conjecture that there exists a
polynomial P
_

C
nn

kl
_
such that P(C
n
k
)P(C
n

l
) = P
_

C
nn

kl
_
to a very specic graph
theory conjecture. Recall that

C
nn

kl
(Denition 26) denotes a specic set of edges.
Lemma 33. Given a minimal k-cover C
n
k
and a minimal l-cover C
n

l
, if there exists a
(kl)-cover C
nn

kl
such that E
_
C
n
k
C
n

l
_
=

C
nn

kl
, then Vizings conjecture is true.
Proof. If there exists a (kl)-cover C
nn

kl
such that E
_
C
n
k
C
n

l
_
=

C
nn

kl
, then
P(C
n
k
)P(C
n

l
) = P
_

C
nn

kl
_
, and P(C
n
k
)P(C
n

l
) I
k
l
. Thus, I
k1
l
I
k
l1
= I
k
l
, and
Vizings conjecture is true.
We will now dene a product graph that specically relates to the

intersection.
Denition 34. Given graphs G and H, the star product GH has vertex set V (G)
V (H) and edge set E(GH) = E(GH)
_
(gh, g

) : g ,= g

and h ,= h

_
.
Proposition 35. Given a k-cover C
n
k
and a l-cover C
n

l
, then E
_
C
n
k
C
n

l
_
=

_
C
n
k
C
n

l
_
.
Proof. This follows directly from Denitions 26 and 34.
We note that C = C
n
k
C
n

l
contains the largest amount of edges such that

C =
C
n
k
C
n

l
. The question that remains is the following.
Conjecture 36. Given minimal k, l-covers C
n
k
, C
n

l
, C
n
k
C
n

l
is a kl-cover.
This is the complement of Vizings conjecture. We observe that we can easily prove
two of the known properties of covers on C
n
k
C
n

l
.
Proposition 37. Given minimal k, l-covers C
n
k
, C
n

l
, every vertex in V (C
n
k
C
n

l
) is con-
tained in a kl-clique.
Proof. Let gh be a vertex in C
n
k
C
n

l
. We must show that gh appears in a kl-clique.
Since C
n
k
, C
n

l
are a k, l-covers respectively, g appears in a k-clique in C
n
k
, and h appears
in an l-clique in C
n

l
. Let gg
1
, . . . , g
k1
be the k-clique in C
n
k
, and let hh
1
, . . . , h
l1

be the l-clique in C
n

l
. We claim
Q =
_
g g
1
, . . . , g
k1

_
h h
1
, . . . , h
l1

_
is a kl-clique in C
n
k
C
n

l
. Let gh and g

be two vertices in Q. If g = g

, then (h, h

) C
n

l
,
since h, h

appear in an l-clique. If h = h

, then (g, g

) C
n
k
, since g, g

appear in an k-
clique. In both cases, (gh, g

) is an edge in C
n
k
C
n

l
. Finally, if g ,= g

and h ,= h

,
then (gh, g

) is an edge in C
n
k
C
n

l
by the denition of the star product. Thus, we have
shown that Q is a kl-clique.
the electronic journal of combinatorics 19(2) (2012), #P1 26
Additionally, we can see that if k and l are strictly greater than two, then C
n
k
C
n

l
has
diameter at most two. This can be seen by choosing any two vertices gh, g

in C
n
k
C
n

l
,
and noting that there must exist a third vertex g

such that g

is adjacent to both
gh and g

. Thus, under these conditions, the diameter of C

n
k
C
n

l
is at most two.
When framing Vizings conjecture in terms of covers and the star product, we can
easily reclaim the complement of a known result by El-Zahar and Pareek [12].
Theorem 38. Given minimal k, l-covers C
n
k
, C
n

l
, such that kl 1 < min(n, n

), then
C
n
k
C
n

l
is a kl-cover.
Proof. Consider any set S of kl 1 vertices in C
n
k
C
n

l
. Let P
n
k
denote C
n
k
-projection of S
(the set of g coordinates such that gh is a vertex in S), and let P
n

l
denote C
n

l
-projection
of S (the set of h coordinates such that gh is a vertex in S). Since kl 1 < min(n, n

),
[P
n
k
[, [P
n

l
[ < min(n, n

). Thus, there exists a vertex g

such that g ,= g

and h ,= h

.
Thus, gh is adjacent to g

, and g

is the common neighbor of S. Since S was a general

set, C
n
k
C
n

l
is a kl-cover.
Since we have shown that C
n
k
C
n

l
is a kl-cover, by Lemma 33, we have shown that
Vizings conjecture holds on this class of graphs. This is the complement of the result
proven in [12]. The restriction placed on the value of r in Theorem 27 now becomes clear.
We only dene the cover representation of I
k
l
when kl l min(n, n

). But since Vizings

conjecture holds whenever kl 1 < min(n, n

), the method of intersecting ideals is dened

only on the as-yet unproven cases of Vizings conjecture.
We conclude by drawing a parallel between universal Grobner bases and Vizings
conjecture based on our experimental investigations with CoCoA Lib [1]. Since a k + 1-
cover is not a proper subset of a k-cover, and an l + 1-cover is not a proper subset of
a l-cover, if any minimal kl-cover can be written as C
n
k
C
n

l
for some minimal C
n
k
, C
n

l
,
then not only is Vizings conjecture true, but replacing
P
_

C
_
= 0, for each C C
nn

kl
,
with
P
_
C
n
k
C
n

l
_
= 0, for each C
n
k
C
n
k
and each C
n

l
C
n

l
,
in Theorem 27 would yield a universal Gr obner basis for I(n, k, n

, l, r = kl 1).
6 Conclusion
In this paper, we approach a canonical NP-complete problem (dominating set) by mod-
eling it as a system of polynomial equations, reducing the model to its universal Gr obner
basis, and then translating the model back to a dierent system of polynomial equa-
tions where the polynomials match one-to-one with domination-critical graphs. This easy
translation between polynomials and subgraphs demonstrates the possibilities opened by
the electronic journal of combinatorics 19(2) (2012), #P1 27
approaching a combinatorial problem via algebraic geometry. In particular, given a prob-
lem such as Vizings conjecture, creating an algebraic formulation is an opportunity for an
entirely new set of tools to try their strength against an old open problem. For example,
during the actual computation of the universal Grobner basis, given that both the initial
ideal representation and the nal universal Gr obner basis have known combinatorial in-
terpretations, is there a graph-theoretic signicance to the intermediate polynomials? Do
Buchbergers S-pair polynomials correspond to a particular subgraph operation? Since
no graph-theoretic counterexample to Vizings conjecture has been found in 50 years, is it
possible that the search for a polynomial counterexample (or proof) is a less prohibitive
challenge?
Additionally, the computational signicance of the linear factor criterion introduced
in this paper is yet to be explored. In this case, the factored form of the both the input
and output ideal is known before the computation even begins. With this combinatorial
knowledge in hand, could a Grobner basis algorithm be specically tailored to avoid
certain types of polynomial expansions when computing on ideals of this form? Finally, a
universal Gr obner basis that is the product of linear factors is not unique to the dominating
set problem; preliminary investigations indicate that other polynomial models of other
combinatorial problems (such as independent set and factoring) share this property.
In short, this paper explores algebraic representations of the dominating set problem,
focusing on a combinatorial interpretation of the universal Grobner basis. The conse-
quence of this result on computation is the subject of future work.
Acknowledgements
The authors would like to thank the anonymous referees for their comments. We also
acknowledge the support of NSF DMS-0729251, NSF-CMMI-0926618, DMS-0240058 and
the Rice University VIGRE program.
References
[1] J. Abbott and A.M. Bigatti. CoCoALib: a C++ library for doing Computations in
Commutative Algebra. Available at http://cocoa.dima.unige.it/cocoalib.
[2] N. Alon. Combinatorial Nullstellensatz. Combinatorics, Prob. and Computing, 8:7
29, 1999.
[3] N. Alon and M. Tarsi. Colorings and orientations of graphs. Combinatorica, 12:125
134, 1992.
[4] E. Babson, S. Onn, and R. Thomas. The Hilbert zonotope and a polynomial time
algorithm for universal Gorbner bases. Advances in Applied Mathematics, 30(3):529
544, 2003.
[5] A. Barcalkin and L. German. The external stability number of the cartesian product
of graphs. Bul. Akad. Stiinte RSS Moldoven., 1(94):58, 1979.
the electronic journal of combinatorics 19(2) (2012), #P1 28
[6] V. Blanco and J. Puerto. Partial Grobner bases for multiobjective integer linear
optimization. SIAM Journal Discret. Math., 23(2):571595, 2009.
[7] B.Stjan, B.Bresar, P.Dorbec, W.Goddard, B.Hartnell, M.Henning, S.Klavzar, and
D.Rall. Vizings conjecture: A survey and recent results, 2009. preprint.
[8] B. Buchberger. An algorithm for nding the basis elements of the residue class ring of
a zero-dimensional polynomial ideal. Journal of Symbolic Computation, 4(3-4):475
511, 2006.
[9] W. Clark and S. Suen. An inequality related to Vizings conjecture. Electronic
Journal of Combinatorics, 7(Note 4), 2000.
[10] P. Conti and C. Traverso. Buchberger algorithm and integer programming. In
Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Al-
gorithms and Error-Correcting Codes, AAECC-9, pages 130139. Springer-Verlag,
1991.
[11] D. Cox, J. Little, and D. OShea. Ideals, Varieties and Algorithms. Springer, New
York, 1998.
[12] M. El-Zahar and C.M. Pareek. Domination number of products of graphs. Ars
Combin., 31:223227, 1991.
[13] S. Eliahou. An algebraic criterion for a graph to be four-colourable. Aportaciones
Matematicas, 6:327, 1992.
[14] K.G. Fischer. Symmetric polynomials and Halls theorem. Discrete Math, 69(3):225
234, 1988.
[15] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of
NP-Completeness. W.H. Freeman and Company, 1979.
[16] J. Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press,
Cambridge, second edition, 1999.
[17] B. Hartnell and D. Rall. Domination in cartesian products: Vizings conjecture. In
Domination in graphs, pages 163189, New York, 1998. Mono. Textbooks Pure and
Appl. Math, Dekker.
[18] C.J. Hillar and T. Windfeldt. An algebraic characterization of uniquely vertex col-
orable graphs. Journal of Combinatorial Theory Series B, 98:400414, 2008.
[19] M. Kreuzer and L. Robbiano. Computational Commutative Algebra I. Springer-
Verlag, 2000.
[20] S. Li and W. Li. Independence number of graphs and generators of ideals. Combi-
natorica, 1:5561, 1981.
[21] J.A. De Loera. Grobner bases and graph colorings. Beitrage zur Algebra und Ge-
ometrie, 36(1):8996, 1995.
[22] J.A. De Loera, C. Hillar, P.N. Malkin, and M. Omar. Recognizing graph theoretic
properties with polynomial ideals. Elect. J. of Combinatorics., 17(1):R114, 2010.
the electronic journal of combinatorics 19(2) (2012), #P1 29
[23] J.A. De Loera, J. Lee, P.N. Malkin, and S. Margulies. Hilberts Nullstellensatz and
an algorithm for proving combinatorial infeasibility. In Proceedings of the twenty-
rst international symposium on Symbolic and algebraic computation, pages 197206.
ISSAC, 2008.
[24] J.A. De Loera, J. Lee, S. Margulies, and S. Onn. Expressing combinatorial op-
timization problems by systems of polynomial equations and the Nullstellensatz.
Combinatorics, Probability and Computing, 18(4):551582, 2009.
[25] L. Lov asz. Stable sets and polynomials. Discrete Mathematics, 124:137153, 1994.
[26] S. Margulies. Computer Algebra, Combinatorics, and Complexity: Hilberts Null-
stellensatz and NP-Complete Problems. University of California at Davis, Ph.D.
Thesis, 2008.
[27] Y. Matiyasevich. A criteria for colorability of vertices stated in terms of edge orien-
tations (in russian). Discrete Analysis (Novosibirsk), 26:6571, 1974.
[28] Y. Matiyasevich. Some algebraic methods for calculation of the number of colorings
of a graph (in russian). Zapiski Nauchnykh Seminarov POMI, 293:193205, 2001.
[29] K. Mizuno and S. Nishihara. Nowhere-zero ow polynomials. Journal of Combina-
torial Theory, Series A, 108(2):205215, 2004.
[30] M. Mnuk. Representing graph properties by polynomial ideals. In Computer Algebra
in Scientic Computing, pages 431444. 4th Inter. Work. on Comp. Alg. in Sci.
Comp., 2001.
[31] A. Simis, W. Vasconcelos, and R. Villarreal. On the ideal theory of graphs. Journal
of Algebra, 167(2):389416, 1994.
[32] D. Sumner and P. Blitch. Domination critical graphs. Journal of Cominatorial
Theory, Series B, 34:6576, 1983.
[33] L. Sun. A result on Vizings conjecture. Discrete Mathematics, 275(1):363366, 2004.
[34] R. Thomas. A geometric buchberger algorithm for integer programming. Mathemat-
ics of Operations Research, 20(4):864884, 1995.
[35] V. Vizing. Some unsolved problems in graph theory. Uspekhi Mat. Nauk, 23:117134,
1968.
the electronic journal of combinatorics 19(2) (2012), #P1 30