DREI'99

Introduction to Domination Theory

 

Stephen T. Hedetniemi

Department of Computer Science

Clemson University

Clemson, SC 29634

 

based on material in

 

Fundamentals of Domination in Graphs

T.W. Haynes

S.T. Hedetniemi

P.J. Slater

Marcel Dekker, Inc.

1998

 

Outline

 

 

 

 

I. Definitions

 

II. Ore's Theorems

 

III. The Domination Inequality Chain

 

IV. Gallai's Theorem

 

Definitions

 

A graph G = (V,E), having a set

 

V = M, V21 ... I vnJ of n vertices, and a set

 

E c V x V of m edges, denoted uv e E.

 

The (open) neighborhood of a vertex u (=- V consists of all vertices adjacent to u, i.e. N(u) = f v I uv E=- E I.

 

The closed neighborhood of a vertex u consists of all vertices adjacent to u together with the vertex u itself, i.e. N[u] = N(u) u tul

If S c V is a set of vertices, then <S> denotes the subgraph of G induced by S, i.e.

 

<S> = (S, E<S>), where E<S> = sxs nE.

 

 

 

 

 

 

 

 

 

 

 

A dominating set S is a minimal dominating set if no proper subset S' c S is a dominating set.

 

The set above is a minimal dominating set.

 

Question: why domination?

 

 

 

 

Variants of a dominating set can also be defined in several different ways:

 

 

The domination number y(G) of a graph G equals the minimum cardinality of a dominating set in G.

 

The upper domination number F(G) of a graph G equals the maximum cardinality of a minimal dominating set in G.

 

Consider the cardinalities (sizes) of all minimal dominating sets in a graph G.

 

y(G) and F(G) equal the minimum and maximum of these cardinalities

 

Ore's Theorems

 

The first two theorems of domination theory are due to Oystein Ore, 1962.

 

Theorem 1. A dominating set S is a minimal dominating set if and only if for every vertex u c S one of the following two conditions holds:

 

(i) u is an isolated vertex of < S >;

 

(ii) there exists a vertex v c V-S for wh N(v) n s = tu).

 

Theorem 2. If G is a graph with no isolated vertices, then the complement V-S of every minimal dominating set S is a dominating set.

 

These two simple theorems suggest many generalizations. Here are six of them...

 

1. Irredundance - conditions (i) and (ii) in Theorem I provide a definition of a new kind of set.

 

Theorem 1. A dominating set S is a minimal dominating set if and only if for every vertex u E=- S one of the following two conditions holds:

 

(i) u is an isolated vertex of <S>;

 

(ii) there exists a vertex v c. V-S for which N(v) n s = ful.

 

Therefore, let us say that a set S is an irredundant set if for every vertex u E=- S one of the following two conditions holds:

 

(i) u is an isolated vertex of <S>;

 

(ii) there exists a vertex v (=- V-S for which N(v) n S = ful.

 

Ore's first theorem can now be restated as:

 

Theorem. [Ore - restated] A dominating set S is a minimal dominating set if and only if S is irredundant.

 

An equivalent definition of an irredundant set can be given as follows:

 

Let S c V be an arbitrary set of vertices and let u E=- S. If there exists a vertex vEEV-S for which N(v) n S = ful then we say that v is a private neighbor of u, with respect to S.

 

We define PN[u,S] = N[u] - N[S-ful] to be the set of private neighbors of a vertex u with respect to the set S.

 

Notice that if u is an isolated vertex of <S>, then u (=- PN[u,S].

 

We say that a set S is irredundant if for every vertex u E=- S, PN[u,S] # 0, i.e. every vertex in S has at least one private neighbor. [Cockayne, Hedetniemi and Miller, 19781

 

In the following example, the complete bipartite graph K5,5satisfies:

 

Y(K5,5) = 2,whileF(K5,5) = 5.

 

 

 

The irredundance number ir(G) equals the minimum cardinality of a maximal irredundant set in G.

 

The upper irredundance number IR(G) equals the maximum cardinality of an irredundant set in G.

 

Theorem. Every minimal dominating set S is a maximal iryedundant set.

 

Corol For any graph G,

ir(G)!~ y(G):!~ F(G):!~ IR(G).

 

Note: E.J. Cockayne and C. Mynhardt are in the process of writing a book on Irredundance in Graphs.

 

By now more than 100 research papers have been written on irredundance in graphs.

 

 

 

 

I

 

 

 

 

 

 

 

2. Ore's Theorem 2 applies to graphs having no isolated vertices, i.e. to graphs having minimum degree 8(G) > 1.

 

Proposition. For any graph G of order n and minimum degree ~! 01

 

(i) y(G)!!~ n, and

 

(ii) y(G) = n if and only if every vertex of an isolated vertex.

 

Theorem [ore, 19621 For any graph G of order n and minimum degree ~! 1, y(G):!~ n/2.

 

Theorem [McQuaig, Shepherd, 1989] For any graph G of order n and minimum degree ~! 2, y(G)!~ 2n/5, except for 7 exceptional graphs.

 

Theorem [Reed, 1996] For any graph G of order n and minimum degree ~! 3, y(G)!!~ 3n/8.

 

? Open. For any graph G of order n and minimum degree ~! 4, y(G) < ??,

 

3. Ore's Theorem 2 asserts that every graph without isolated vertices has two disjoint dominating sets. In fact, every such graph has two disjoint minimal dominating sets.

 

This suggests the following definition [Cockayne and Hedetniemi, 1977]:

 

The domatic number d(G) equals the maximum order of a partition of V(G) into dominating sets. [spellchecker??]

 

Equivalently, one can say that d(G) equals the maximum number of disjoint dominating sets that can be found in G (i.e. we don't have to have a strict partition of V(G)).

 

Ore's Theorem 2 therefore asserts that for every graph G without isolated vertices, d(G) > 2.

 

Bohdan Zelinka, Czech Republic has done a lot of work on domatic numbers.

 

4. Let S c V be a set of vertices having some property P of interest. We say that S is a P-set. In particular, consider a dominating set S which also has one of the following properties P, defined in terms of the subgraph < S > induced by S:

 

1. < S > is an arbitrary graph.

 

i---> S is a dominating set

 

2. <S> has no edges, i.e. S is an independent set (a set S is called independent if no two vertices in S are adjacent).

 

F4 S is an independent dominating set

[chess folklore]

 

3. < S > has no isolated vertices, i.e. < S > has minimum degree > 1.

 

F4 S is a total dominating set

[Cockayne, Dawes and Hedetniemi, 1980]

 

4. < S >is a connected graph.

 

F--> S is a connected dominating set

[Sampathkumar and Walikar, 1979]

 

5. <S> has a perfect matching.

 

F--> S is a paired dominating set

[Haynes and Slater, 1995]

 

6. < S > has no cycles, i.e. < S > is acyclic.

 

F-> S is an acyclic dominating set

[Hedetniemi, Hedetniemi and Rall, 19981

 

7. <S> has maximum degree A:!~ k, te, S is called k-dependent.

 

F-> S is a k-dependent dominating set

 

[Favaron, Hedetniemi, Hedetniemi and Rall, 1999]

 

8. <S> is a bipartite graph.

 

~~ S is a bipartite dominating set

[Hedetniemi, Hedetniemi and Laskar, 1999.1

 

? Ore's Theorem 2 suggests that in general we could ask: given a property P, under what conditions does a graph G have two disjoint P-sets which are also dominating sets?

 

for example,

 

? 1. When does G have two disjoint independent dominating sets?

 

? 2. When does G have two disjoint total dominating sets?

 

? 3. When does G have two disjoint connected dominating sets?

 

? 4. When does G have two disjoint paired dominating sets?

 

? 5. When does G have two disjoint acyclic dominating sets?

 

? 6. For what values of k, does G have two disjoint k-dependent dominating sets?

 

? 7. When does G have two disjoint bipartite dominating sets?

 

Notice that every graph G without isolated vertices has two disjoint dominating sets, one of which is an independent dominating set.

 

? Thus, one could ask: when does a given graph G have two disjoint dominating sets of two given types?

 

Actually, Ore's Theorem 2 suggests two types of questions:

 

? 0) when is the complement V-S of a (dominating) P-set S also a (dominating) P-set?

 

? (ii) when does the complement V-S of a (dominating) P-set S contain a (dominating) P-set?

 

5. Ore's Theorem 2 says that the complement of every minimal dominating set contains a minimal dominating set.

 

This suggested to [Kulli and Sigarkanti, 19911 the following. Consider all y-sets S of a graph G, i.e. dominating sets S for which ISI = y(G).

 

The inverse domination number Y(G) equals the minimum cardinality of a dominating set in the complement of a y-set of G.

 

? Kulli and Sigarkanti claim that for any graph G, Y(G) < p (G), where p (G) equals the maximum number of vertices in an independent set. However, we have been unable to verify their proof nor have we been able to either construct our own proof or a counterexample to this claim!!

 

The inverse domination number, however, suggested to Markus, Hedetniemi, Hedetniemi, Laskar and Slater [work in progress] the following line of research...

 

 

 

Define the dual domination number yy(G) to equal the minimum sum of the cardinalities of two disjoint dominating sets in a graph G.

 

Proposition. For any graph G without isolated vertices,

One can also seek the minimum sum of the cardinalities of two disjoint dominating sets, one of which must be an independent dominating set. Denote this sum iy(G).

 

Proposition. For any graph G without isolated vertices,

 

 

 

 

6. Ore's Theorem 2 says that every graph without isolated vertices has two disjoint minimal dominating sets. Consider the cardinalities of these two sets. In fact, consider the cardinalities of all minimal dominating sets in a graph G.

 

For the graph K5,5 above, one can see that there are only two sizes of minimal dominating sets, i.e. 2 and S.

 

Yet the path Pq has minimal dominating sets of sizes 3A and 5. In this case we say that the minimal dominating sets interpolate (are consecutive integers).

 

? Under what conditions on a graph G, or for what families of graphs G, do the minimal dominating sets interpolate?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

III. The Domination Inequality Chain

 

We say that a set S in independent if no two vertices in S are adjacent.

 

We define i(G) to equal the minimum cardinality of a maximal independent set in G. This is called the independent domination number of G.

 

Let p (G) equal the maximum cardinality of an independent set in G. This is called the independence number of G.

 

Notice, for the complete bipartite graph K5,5, we have i(K5,5) = 5 and B(K5,5) = 5- See also the following example.

 

 

 

 

 

G has maximal independent sets of sizes 3. 4 and 5.

Hence, i(G) = 3 and P(G) = 5.

Proposition 1. An independent set S is a maximal independent set if and only if it is both independent and dominating.

 

Proposition 2. Every maximal independent set is a minimal dominating set.

 

The following Domination Inequality Chain is a consequence of the previous observations:

 

[Cockayne, Hedetniemi and Miller, 1978] For any graph G,

 

ir(G) < 7(G) < i(G):!~, P(G):!~ ]F(G)!~, IR(G).

 

More than 100 published papers have studied various aspects of this inequality chain.

 

Consider the following containment relations between maximal independent sets, minimal dominating sets and maximal irredundant sets.

 

 

Consider the following:

 

An independent set S is maximal independent

 

iff (vvc-V-S)[Sufvl is not independent]

 

iff (vvE=-V-S)(3uc=-S)[uv c= E(G)]

 

iff S is a dominating set (!)

 

Next ...

 

A dominating set S is a minimal dominating set

 

iff (VUES)[S-fU) iSnot a dominating set]

 

iff either u is an isolated vertex in < S > or

(3vEV-S)[ JN(v) n s = full I

 

iff S is irredundant (!)

 

An irredundant set S is maximal irredundant

 

iff (vvEV-S)[Sutv) is not irredundantl

 

iff ...

 

Not so fast!

 

Note carefully the difference between: ,

 

I-maximal and maximal

 

1-minfirnal and minimal

 

 

When is 1-maximal equivalent to maximal? When the property P is hereditary, i.e. every subset of a P-set is also a P-set. Notice that every subset of an independent set is an independent set, i.e. independence is a hereditary property.

 

 

 

 

When is 1-minimal equivalent to irninimal? When the property P is superhereditary, i.e. every superset of a P-set is also a P-set.

 

Notice that every superset of a dominating set is also a dominating set. Thus, the property of being a dominating set is superhereditary.

 

Notice also that every subset of an irredundant set is an irredundant set. Thus, irredundance is hereditary.

 

Therefore, we can say:

 

an irredundant set S is maximal irredundant

 

 

 

 

Define the private neighbor count pnc(S) of a set S of vertices to equal

 

pnc(S) = Itur=S I PN[u,S]# 011

 

i.e. pnc(S) equals the number 'of vertices in S which have at least one private neighbor.

 

Notice that if a set S is irredundant. then

 

pnc(S) = ISI.

 

One can now show that an irredundant set S is maximal irredundant

 

We say then that a set S is external redundant

 

Define er(G) and ER(G) to equal the minimum and maximum cardinalities, respectively, of a minimal external redundant set in G.

 

Theorem. Every maximal irredundant set in a graph G is also a minimal external redundant set.

 

This raises the interesting question:

 

? a set S is a minimal external redundant set iff ??? i.e. what comes next in the domination inequality chain?

 

Here is another interesting question, first raised by Slater:

 

? does there exist a'natural'property P such that every minimal P-set is a maximal independent set?

 

 

IV. Gallai's Theorem

 

Define a vertex cover to be a set S of vertices having the property that for every edge uvE=-E, either uE=-S or vE=-S (or both).

 

The vertex covering number, denoted a(G), equals the minimum cardinality of a vertex cover in G.

 

Theorem [Gallai, 19591 For any graph G of

ordern,

 

a(G) + p(G) = n.

 

This is called the Gallai Theorem, and theorems of this form are called Gallai Theorems.

 

Consider the following example:

 

Notice in the following graph,

p(G) = 5

a(G) = 4

n = 9.

It is easy to see that the complement V-S of every vertex cover S is an independent set, and conversely, the complement of every indevendent set is a vertex cover.

 

Many Gallai Theorems exist for various types of domination parameters.

 

Here is just a sample:

 

 

 

 

Theorem. For any graph G of order n,

 

  1. [Gallail] a (G) + p (G) = n.