# Domination Theory in Graphs

E. Sampathkumar (University of Mysore, India) and L. Pushpalatha (Yuvaraja's College, India)
DOI: 10.4018/978-1-5225-9380-5.ch001
Available
\$37.50
No Current Special Offers

## Abstract

The study of domination in graphs originated around 1850 with the problems of placing minimum number of queens or other chess pieces on an n x n chess board so as to cover/dominate every square. The rules of chess specify that in one move a queen can advance any number of squares horizontally, vertically, or diagonally as long as there are no other chess pieces in its way. In 1850 enthusiasts who studied the problem came to the correct conclusion that all the squares in an 8 x 8 chessboard can be dominated by five queens and five is the minimum such number. With very few exceptions (Rooks, Bishops), these problems still remain unsolved today. Let G = (V,E) be a graph. A set S ⊂ V is a dominating set of G if every vertex in V–S is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set.
Chapter Preview
Top

## Introduction

The study of Domination in Graphs originated around 1850 with the problems of placing minimum number of queens or other chess pieces on an chess board so as to cover/dominate every square. The rules of chess specify that in one move, a queen can advance any number of squares horizontally, vertically or diagonally as long as there are no other chess pieces in its way. In 1850 enthusiasts who studied the problem came to the correct conclusion that all the squares in an 8 x 8 chessboard can be dominated by five queens and five is the minimum such number. With very few exceptions (Rooks, Bishops), these problems still remain unsolved today.

Let be a graph. A set is a dominating set of G if every vertex in is adjacent to some vertex in D. The domination number of G is the minimum cardinality of a dominating set.

Figure 1.

­

is a dominating set and .Top

## Applications

• 1.

Berge (1973) in his book “Graphs and Hypergraphs” mentions the problem of keeping all points in a network under the surveillance of a set of radar stations. A number of strategic locations called cells are kept under the surveillance of radar. Radar in cell can survey the locations or . Similarly, can be surveyed by radar located at or .

What is the minimum number of radar stations needed to survey all locations? It is the domination number of the network.

## Complete Chapter List

Search this Book:
Reset