基于鄰接矩陣判斷圖的Cordial性

卞洪亞

（廈門工學院理學院，福建廈門361021）

基于鄰接矩陣判斷圖的Cordial性

卞洪亞

（廈門工學院理學院，福建廈門361021）

摘要：給出了圖G是Cordial圖的充分必要條件；對于給定任意n階圖，給出如何利用計算機判斷其Cordial性；利用計算機，給出找出所有n階可Cordial圖的方法.

關鍵詞：Cordial圖；鄰接矩陣；簡單圖

在文獻［1］中，Cahit提出了Cordial圖的概念，并指出完全二部圖是Cordial圖，文獻［2-7］討論了一些特殊圖的Cordial性，但還有很多圖的Cordial性還沒有解決.為了方便研究和驗證圖的Cordial性，本文給出了鄰接矩陣判別法來判斷圖的Cordial性.它的優(yōu)點在于可以利用計算機快速驗證圖的一個標號是不是Cordial標號，這為研究圖的Cordial性節(jié)約了大量時間.還可以利用計算機批量判斷階數(shù)比較小的圖的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的頂點集合的基數(shù)，以e0（G,f）和e1（G,f）分別表示值為0、1的邊集合的基數(shù).

定義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的邊的數(shù)目，且A′（G）= A（G）.

2　圖的Cordial性的矩陣判別法

定理1設A為圖G的鄰接矩陣，P為對角線上元素只能為1或-1的對角矩陣.圖G是Cordial圖的充分必要條件，是存在對角陣P使得

證明由鄰接矩陣的定義，可知aij≥0；現(xiàn)在規(guī)定：|| aij是連接vi和vj的邊的數(shù)目，若vi和vj兩點的標號相同時，則aij≥0；若vi和vj兩點的標號不相同時，則aij≤0 .在新的規(guī)定下，原始的鄰接矩陣就相當于圖G所有頂點都標0或1的情況下對應的矩陣.不妨設圖G所有頂點都標0.如果改變圖G中頂點vi的標號，就相當于改變鄰接矩陣中第i行和第i列元素的符號，又等價于鄰接矩陣同時左乘和右乘初等陣Pn（i）.若改變圖G中k個頂點的標號，即把k個頂點標為1，等價于鄰接矩陣同時左乘和右乘k個上述初等陣，把這k個初等陣的乘積記為Pn，又等價于鄰接矩陣左右兩邊同時乘以Pn.

因此原命題得證.

3　圖的Cordial性的矩陣判別法在計算機上的實現(xiàn)

1）給定任意n階圖，判斷其Cordial性.

若給定的是Cordial圖，則必定有標0的頂點數(shù)和標1的頂點數(shù)相等或相差一個，不妨假設標1的頂點數(shù)小于等于標0的頂點數(shù)，對應于矩陣就相當于單位矩陣中有［n/2］個1變?yōu)?1.我們把所有這種變化表示出來，主要用了MATLAB中nchoosek（v，k）的命令來實現(xiàn)，具體MATLAB代碼見下面：

%給定任意n階圖，判斷其Cordial性，并給出所有的Cordial標號. A為n階圖的鄰接矩陣.

2）找出所有n階可Cordial圖，圖是簡單圖.

若一個n階圖是Cordial圖，則必定存在標號滿足定義，把所有標有1的頂點排在前面，之后都是標有0的頂點，這樣其對應的變換矩陣可以唯一地表示為對角陣，對角線上元素先為-1，之后的為1.矩陣的跡為0或者1.變換矩陣定下來，我們就要把所有n階圖的鄰接矩陣表示出來，在同構(gòu)的意義下，我們用十進制的數(shù)二進制的形式來填充矩陣.具體操作見下面MATLAB代碼：

參考文獻：

［1］CAHIT I. Cordial Graphs：A Weaker Version of Graceful and Harmonious Graphs［J］. Ars Combinatoria, 1987, 23：201-208.

［2］BENSON M, LEE S. On cordialness of regular windmill graphs［J］. Congressus Numerantium, 1989, 68：49-58.

［3］KUO D, CHANG G J, KWONG Y H H. Cordial labeling of mKn［J］. Discrete Mathematics, 1997, 169：121-131.

［4］LIMAYE N B. Cordial Labelings of Some Wheel Related Graphs［J］. JCMCC, 2002, 41：203-208.

［5］ANDAR M M, BOXWALA S, LIMAYE N B. On the Cordiality of Corona Graphs［J］. Ars Combinatoria, 2006, 78：179-199.

［6］CAHIT I. On Cordial and 3-Equitbale Labeling of Graphs［J］. Utilitas Math, 1990, 37：189-198.

［7］GALLIAN J A. A dynamic survey of graph labeling, The Electronic［J］. Journal of Combinatorics, 2000（6）：49-56.

Judgment of the Cordiality of Graphs Based on Adjacent Matrix

BIAN Hongya
（School of Science, Xiamen Institute of Technology, Xiamen 361021, China）

Abstract：The necessary and sufficient condition for Graph G to be cordial graph is given in this paper. The ways to judge the cordiality of any n-order graph and find out all n-order cordial graphs with a computer are also given in the paper.

Key words：cordial graph；adjacent matrix；simple graph

中圖分類號：O157.5

文獻標識碼：A

文章編號：1008-2794（2016）02-0096-04

收稿日期：2015-09-29

通信作者：卞洪亞，碩士研究生，研究方向：代數(shù)圖論，E-mail：kylj007@163.com.