Queens graphs

Lowell W. Beineke; Izak Broere; Michael A. Henning

doi:10.1016/S0012-365X(98)00392-6

Queens graphs

Lowell W. Beineke, Izak Broere, Michael A. Henning

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

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	https://doi.org/10.1016/S0012-365X(98)00392-6
Publication status	Published - 28 Aug 1999
Externally published	Yes

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(98)00392-6

Cite this

@article{7ebcb487f78946f5a07db9a282b68909,

title = "Queens graphs",

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 K1,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 Kn × Pm and C2n × Pm 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 K4,4, K1,3,3, K2,2,2 or K1,1,2,2. It is also shown that K3,4 - e is not a queens graph.",

author = "Beineke, {Lowell W.} and Izak Broere and Henning, {Michael A.}",

year = "1999",

month = aug,

day = "28",

doi = "10.1016/S0012-365X(98)00392-6",

language = "English",

volume = "206",

pages = "63--75",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Queens graphs

AU - Beineke, Lowell W.

AU - Broere, Izak

AU - Henning, Michael A.

PY - 1999/8/28

Y1 - 1999/8/28

N2 - 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 K1,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 Kn × Pm and C2n × Pm 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 K4,4, K1,3,3, K2,2,2 or K1,1,2,2. It is also shown that K3,4 - e is not a queens graph.

AB - 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 K1,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 Kn × Pm and C2n × Pm 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 K4,4, K1,3,3, K2,2,2 or K1,1,2,2. It is also shown that K3,4 - e is not a queens graph.

UR - http://www.scopus.com/inward/record.url?scp=0042208685&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(98)00392-6

DO - 10.1016/S0012-365X(98)00392-6

M3 - Article

AN - SCOPUS:0042208685

SN - 0012-365X

VL - 206

SP - 63

EP - 75

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Queens graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this