Domination and Separation Problems on Chessboard Graphs

Abstract

In graph theory, a graph G = (V, E) is a finite undirected simple graph formed by newlineconsidering the set of objects as vertices and pair-wise relation between the objects newlineas edges. Domination in graphs is regarded as the most interesting area of research newlinein graph theory worldwide. This concept started with a famous chessboard problem in 1862 when C. F. De Jaenisch considered the problem of determining a newlineminimum number of queens that can be placed on a square chessboard so that newlineevery square is either occupied or covered by a queen. After a century, this problem was accepted as the domination number of the queens on a chessboard. In newlinegraph theory, a chessboard graph G is a graph that represents all legal moves of newlinea chess piece on a chessboard. Each vertex of a chessboard graph represents a newlinesquare on a chessboard, and each edge represents a legal move from one square newlineto another. newline