卞洪亚

（厦门工学院理学院，福建厦门361021）

基于邻接矩阵判断图的Cordial性

卞洪亚

（厦门工学院理学院，福建厦门361021）

摘要：给出了图G是Cordial图的充分必要条件；对于给定任意n阶图，给出如何利用计算机判断其Cordial性；利用计算机，给出找出所有n阶可Cordial图的方法.

关键词：Cordial图；邻接矩阵；简单图

在文献［1］中，Cahit提出了Cordial图的概念，并指出完全二部图是Cordial图，文献［2-7］讨论了一些特殊图的Cordial性，但还有很多图的Cordial性还没有解决.为了方便研究和验证图的Cordial性，本文给出了邻接矩阵判别法来判断图的Cordial性.它的优点在于可以利用计算机快速验证图的一个标号是不是Cordial标号，这为研究图的Cordial性节约了大量时间.还可以利用计算机批量判断阶数比较小的图的Cordial性，这也为Cordial图研究指明方向.

1　基本概念

本文主要考察无向有限的简单图.设f是图G的顶点集合V（G）上的双值标号，即对于每一个顶点v∈V（G），定义f（v）= 0或1；再由f（uv）=| f（u）- f（v）|导出G的边集合E（G）上的标号.以V0（G,f）和V1（G,f）分别表示标0、1的顶点集合的基数，以e0（G,f）和e1（G,f）分别表示值为0、1的边集合的基数.

定义1［1］若图G的标号f满足：则称f是Cordial标号，存在Cordial标号的图称为Cordial图.

记XA为矩阵An中所有元素之和的一半，即

记Pn（i）为n阶单位阵的（i,i）位置的元素1改为-1的初等矩阵.

设V（G）=｛v1,v2,…,vn｝，则G可用邻接矩阵表示：其中aij是连接vi和vj的边的数目，且A′（G）= A（G）.

2　图的Cordial性的矩阵判别法

定理1设A为图G的邻接矩阵，P为对角线上元素只能为1或-1的对角矩阵.图G是Cordial图的充分必要条件，是存在对角阵P使得

证明由邻接矩阵的定义，可知aij≥0；现在规定：|| aij是连接vi和vj的边的数目，若vi和vj两点的标号相同时，则aij≥0；……