Chessboard graphs, related designs, and domination parameters
This paper is evidently written for readers who are not specialists in graph theory. It starts with an introduction into graph terminology. Then some classical chessboard problems are described, namely those concerning queens and rooks. Thereafter designs are described and their graphs defined. The chessboard representation of a graph (which is a subgraph of the rook graph) is introduced. Such a representation looks out like a chessboard in which white and black squares occur (not necessarily as on an usual chessboard). The white squares represent the vertices; two vertices are adjacent if and only if the corresponding squares are on the same row or on the same column. The theorems deal with the domination number and the independence number of the line graph of the graph of the \((b,v,r,k,\lambda)\) BIBD and the domination number of the line graph of the classical projective plane \(\text{PG}(2,n)\).
scientific article; zbMATH DE number 1326610