Discrete Mathematics 126 (1994) 403-406 403

North-Holland

Note

A generalization of Vizing’s
theorem on domination
Jason Fulman
Department of Mathematics, Harvard University, Cambridge, MA 02138. USA

Received 24 September 1991

Abstract

Vizing (1965) established an upper bound on the size of a graph with a given domination number.
We generalize Vizing’s bound so that it takes into consideration the graph’s maximum degree. As an
application, we shorten the proof of Sanchis’ (1991) upper bound on the size of graphs with
domination number at least three and no isolated vertices.

1. Definitions and basic lemmas

The graphs considered here are finite and simple. V(G) and E(G) will denote the
vertex set and edge set of a graph G, and uv an edge between vertices u and v. The
neighborhood of a vertex v is N(v)= ( u 1uv~E} and its closed neighborhood is
N[u] = N(v)u(u}. A dominating set of a graph G is a set D of vertices of G such that all
vertices of V-D are adjacent to some vertex of D. The minimum cardinality taken
over all dominating sets of G is denoted by y(G) and is called the domination number of
G. ( V) means the graph induced by a set of vertices V. p(G),q(G), and A(G) will
denote the order, size, and maximum degree of a graph G, respectively. When no
ambiguity exists as to the graph in question, the (G) will be omitted.

Correspondence to: J. Fulman, Department of Mathematics, Harvard University, Cambridge,

0012-365X/94/$07.00 0 1994-Elsevier Science B.V. All rights reserved

2. Main results

Theorem 2.1. (Vizing [2]). If G is a graph with domination number y 22, then q(G)<
LGwkw+~)J.
Vizing showed Theorem 2.1 to be the best possible by constructing a family of
graphs that attains the upper bound in Theorem 2.1. All members of this family of
graphs satisfy A=p-y (note that for any graph G, A(G)<p(G)-y(G)). This suggests
that when A <p-y, it may be possible to improve Vizing’s result. Theorem 2.2,
inspired by Vizing’s method of proof, shows that this is the case.

Theorem 2.2. ZfG is a graph, then q(G)bL+[(p-y)(p-y++)-A(p-y-A)]].

Proof. First assume that y(G) > 3. Let x be a vertex of degree A. To bound q(G), we use
the relation 2q(G)=CveN[xldeg(v)+~“sv_N[xldeg(v). Clearly, CvE.IX1deg(4dA
(A + 1). There are two contributions to the remaining summand; the first contribution
is from edges between N [x] and V-N [ x ] , and the second contribution is from edges
in ( V-N [x] ). To compute the first contribution, note that a neighbor x1 of x is
adjacent to at most (p-A - y + 1) of the (p-A - 1) elements of V-N [xl, for other-
wise x,x1, and V-N [x] -N [xl] would be a dominating set of G of size < y- 1. To
compute the second contribution, note that y( ( V-N [x] )) 2 y(G) - 12 2. Applying
Vizing’s theorem, we obtain q(( V- N[x]))<i(p- A-y)(p- A-y+2). Thus q(G)<
L:C(P-A-~)(P-A--_+~)+A(A+~)+A(P-A--_++)~~=L~C(P-Y)(P-~+~)
- A (p - y - A)] J. The result also holds when y(G) < 3, since adding 2 isolated vertices
to G gives a graph G’ with y(G’)>3, q(G’)=q(G), A(G’)=A(G), and p(G’)-y(G’)=
P(G) -Y(G). q

It would be interesting to determine for what values of A the result in Theorem 2.2
can be improved. By Vizing’s work, if A = p - y, the result is the best possible. We now
show that when A = p - y - 1, the bound from Theorem 2.2 can be improved by exactly
1 edge.

Theorem 2.3. If G is a graph with A =p -y - 1, then

q(G)<

and this result is best possible.

Proof. By Theorem 2.2,

q(G)6L)C(p-y)(P-Y+l)+llJ=
(‘-;+I>.
 Generalization of Vizing’s theorem on domination 405

Since both A and the p---y are unaffected by the removal of isolated vertices, we can
assume that G has no isolated vertices. Tracing through the proof of Theorem 2.2 and
letting x denote a vertex of degree A, we see that in any graph attaining this bound,
N [x] consists of vertices of degree A. We also recall that ( V-N [xl) has y vertices
and exactly one edge ab, and that each element of N(x) must be adjacent to exactly
two elements of V-N [x]. It follows that each element of N(x) must be adjacent to at
least one of a or b, for otherwise a smaller dominating set of G could be found, making
use of the edge ab. These considerations imply that G is connected. Since x is an
arbitrary vertex of degree A and N [x] consists of vertices of degree A, connectedness
of G shows G is regular of degree A. Since a and b contribute to 24 - 2 of the 24 edges
between N(x) and V- N[x], it is straightforward that A 62. The only regular,
connected graph of degree one consists of two vertices joined by an edge, and the only
regular, connected graphs of degree two are cycles. It is easy to see that in neither case
can the bound of Theorem 2.2 be strict.
A (p-3)-regular graph G with y = 2 (for instance, a 5-cycle) shows that the result of
this theorem is the best possible. To construct examples with ~23, simply add to
G isolated vertices. 0

The proof of Theorem 4 in [l] involves complicated reasoning for all graphs
satisfying A d p - y - 1. In Theorem 2.5, we offer a shorter proof for this case, and show
that the result still holds even if G has isolated vertices.

Theorem 2.4 (Sanchis Cl]). If G has no isolated vertices and y(G)> 3, then

Theorem 2.5. If G is a graph with A <p - y - 1, then

Proof. Observe by calculus that the bound from Theorem 2.2 is parabolic with
a minimum at A = :(p - y). It therefore suffices to apply the bound for A = p - y - 1 and
A = 1. In both cases, we then conclude that

q(G)dL+C(p-y)(p-y+ l)+ l] J= ‘-;+’

When A = 1, this bound is clearly unattainable. By Theorem 2.3, this bound is also
unattainable for A = p - y - 1. 0
406 .I. Fulman

Acknowledgment

This work was done at the University of Minnesota, Duluth, under the supervision
of Joseph A. Gallian and with support from the NSF (Grant number DMS-9000742)
and the NSA (Grant number MDA 904-88-H-2027). The author appreciates the
comments of both Joseph A. Gallian and the referee.

References

[l] L.A. Sanchis, Maximum number of edges in connected graphs with a given domination number,
Discrete Math. 87 (1991) 65-72.
[2] V.G. Vizing, A bound on the external stability number of a graph, Dokl. Akad. Nauk. 164 (1965)
729-731.