## Abstract

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 if and only if some diagonal or line of A contains the corresponding 1's. A basic question is the determination of which graphs are queens graphs. We establish that a complete block graph is a queens graph if and only if it does not contain K_{1,5} as an induced subgraph. A similar result is shown to hold for trees and cacti. Every grid graph is shown to be a queens graph, as are the graphs K_{n} × P_{m} and C_{2n} × P_{m} for all integers n,m ≥ 2. We show that a complete multipartite graph is a queens graph if and only if it is a complete graph or an induced subgraph of K_{4,4}, K_{1,3,3}, K_{2,2,2} or K_{1,1,2,2}. It is also shown that K_{3,4} - e is not a queens graph.

Original language | English |
---|---|

Pages (from-to) | 63-75 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 206 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 28 Aug 1999 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics