Queens graphs (Q1304808)

The queens graph of a \((0,1)\)-matrix \(A\) is the graph whose vertices correspond to the 1's in \(A\) and in which two vertices are adjacent iff some diagonal or line of \(A\) contains the corresponding 1's. It is obvious that a given queens graph generally has many representations as a binary matrix. Therefore the authors think it is better to represent queens graphs in the plane lattice which is considered in Chapter 2 and formalized in Theorem 1. Moreover the concept of direction of the edges in such a plane representation is introduced. Direction decompositions are considered in Chapter 3. In this paper the basic question investigated is which graphs are queens graphs, and the authors are concerned with complete-block graphs, trees and cacti (Chapter 4), products of graphs (Chapter 5), complete multipartite graphs (Chapter 6) and subgraphs of queens graphs (Chapter 7). A complete-block graph is a connected graph in which every block is complete. A cactus is a connected graph, every block of which is a \(K_2\) or a cycle. A grid graph is the Cartesian product \(P_m\times P_n\) of two paths. The authors get the following results: (1) A complete-block graph is a queens graph iff it does not contain \(K_{1,5}\) as an induced subgraph (Theorem 3). (2) A tree is a queens graph iff it has maximum degree at most 4 (Corollar 1). (3) A cactus is a queens graph iff it does not contain \(K_{1,5}\) as an induced subgraph (Theorem 4). (4) Every grid graph is a queens graph (Theorem 5). (5) For all integers \(n,m\geq 2\) the graphs \(K_n\times P_m\) and \(C_{2n}\times P_m\) are queens graphs (Theorems 6 and 7). (6) A complete multipartite graph is a queens graph iff it is a complete graph or an induced subgraph of one of the following: \(K_{4,4}\), \(K_{1,3,3}\), \(K_{2,2,2}\) or \(K_{1,1,2,2}\) (Theorem 13). (7) \(K_{3,4}-e\) is not a queens graph (Theorem 14).