Domination Theory in Graphs

Domination Theory in Graphs

E. Sampathkumar, L. Pushpalatha
Copyright: © 2020 |Pages: 23
DOI: 10.4018/978-1-5225-9380-5.ch001
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

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 978-1-5225-9380-5.ch001.m01 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 978-1-5225-9380-5.ch001.m02 be a graph. A set 978-1-5225-9380-5.ch001.m03 is a dominating set of G if every vertex in 978-1-5225-9380-5.ch001.m04 is adjacent to some vertex in D. The domination number 978-1-5225-9380-5.ch001.m05 of G is the minimum cardinality of a dominating set.

Figure 1.

­

978-1-5225-9380-5.ch001.f01
978-1-5225-9380-5.ch001.m06 is a dominating set and 978-1-5225-9380-5.ch001.m07.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 978-1-5225-9380-5.ch001.m08 called cells are kept under the surveillance of radar. Radar in cell 978-1-5225-9380-5.ch001.m09 can survey the locations 978-1-5225-9380-5.ch001.m10 or 978-1-5225-9380-5.ch001.m11. Similarly, 978-1-5225-9380-5.ch001.m12 can be surveyed by radar located at 978-1-5225-9380-5.ch001.m13or 978-1-5225-9380-5.ch001.m14.

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