邓毅雄

（华东交通大学软件学院，江西南昌330013）

Deng Yixiong

（School of Software，East China Jiaotong University，Nanchang 330013，China）

本文讨论的图都是简单无向图，文中未加说明的术语和符号参阅文献[1][2]。

L.W.Beineke等[3]引入了queens-图的概念，并且证明了在一定条件下的完全块图、树、Kn×Pm、Pn×Pm，C2n×Pm等是queens-图，并解决了二部及多部图的问题。到目前，这方面的研究成果比较少，另外的结果有:证明了θ-图是queens-图，并给出了B(m，n，r)图是queens-图的充分必要条件[4]；讨论了queens-图的构造问题，也得到了一些queens-图[5]。

1 定义及引理

设A是（0，1）-矩阵。一个图称为A的queens-图，记为Q(A)，如果这个图的点与A中的1相对应，图的两个点邻接当且仅当A中对应的1同在某线或对角线上。（这里的“线”是指矩阵的行或列。）

我们称一个图G是queens-图，如果存在某（0，1）-矩阵A，使得G是A的queens-图。注意到，给出一个（0，1）-矩阵，很容易获得其对应的queens-图，但是，给出一个图G，判断它是否为queens-图，却常常不是一件容易的事情。所以，这方面研究的一个主要问题是:哪些图是queens-图？

文献[3]给出了下面两个引理:

引理1[3]图G是queens-图当且仅当它的点可以对应坐标(i，j)，并且两个不同的点(i，j)和(k，l)邻接当且仅当1i=k，或 2j=l，或 3i+j=k+l，或4i-j=k-l。

引理2[3]如果图G是queens-图，那么G不包含导出子图K1，5。

引理1给出的4个条件，依次分别指的是两个点在同一行、列、主对角线和斜对角线上，用于queens-图的验证和判断。引理2给出的queens-图的必要条件是基于矩阵只有4条“线”，它在判断一个图不是queens-图时，非常有用。

确定一个图G是否为queens-图，就是构造对应的（0，1）-矩阵A，也就是确定1的位置，或者说是1的坐标(i，j)，而1的位置就是图G的点的位置，所以，图G是否为queens-图，就是看能否构造满足定义或者说满足引理1要求的点的坐标(i，j)。……