Name
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 2 n × 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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0012-365X(98)00392-6 | Discrete Mathematics |
DocType | Volume | Issue |
Journal | 206 | 1 |
ISSN | Citations | PageRank |
Discrete Mathematics | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lowell W. Beineke | 1 | 204 | 86.82 |
| Izak Broere | 2 | 143 | 31.30 |
| Michael A. Henning | 3 | 1865 | 246.94 |