Queens graphs
type: Item
instance of: scholarly article
title: Queens graphs
zbMATH Open document ID: 0935.05064
DOI: 10.1016/S0012-365X(98)00392-6
author: L. W. Beineke
author: Izak Broere
author: Michael A. Henning
published in: Discrete Mathematics
publication date: 2000-05-04T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 1340364
zbMATH Keywords: queens graph
zbMATH Keywords: representations
zbMATH Keywords: tree
zbMATH Keywords: cactus
zbMATH Keywords: grid graph
reviewed by: Heinz-Joachim Presia
MaRDI profile type: Publication
full work available at URL: s0012-365x(98)00392-6
OpenAlex ID: W4213354068
description: scientific article; zbMATH DE number 1340364