Δ（G）≤2的圖的Cordial性

徐麗平，李治

（長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州434023）

1987年Cahit引出Cor dial圖的概念［1］，給定圖G的頂點(diǎn)集合V（G）一個(gè)0－1標(biāo)號(hào)，記為f，以導(dǎo)出G的邊集合E（G）上的標(biāo)號(hào)，記Vi＝Vi（G）＝｛u／u∈V（G），f（u）＝i｝，Ei＝Ei（G）＝｛uv／uv∈E（G），f（uv）＝i｝，i＝0，1。并以vi（G），ei（G）分別表示它們的基數(shù)，若圖G存在一個(gè)標(biāo)號(hào)f，使得則稱G是Cor dial圖，f是一個(gè)Cordial標(biāo)號(hào)；若v0（G）＝v1（G），e0（G）＝e1（G），則稱G 是嚴(yán)格Cordial圖，f是一個(gè)嚴(yán)格Cordial標(biāo)號(hào)。這種標(biāo)號(hào)引起人們的廣泛興趣，已有很多論文如文獻(xiàn)［1－7］研究了各種圖的Cordial性，但是關(guān)于并圖的Cordial性的研究?jī)H限于分支十分簡(jiǎn)單的圖，如關(guān)于圈的并只限于2個(gè)分支Cm∪Cn［2］，或雖是多個(gè)分支但各圖的階數(shù)必須相同的情況［2］，而對(duì)于路與圈的并圖的Cordial性尚無(wú)人考慮。下面，筆者研究Δ（G）≤2的圖的Cordial性，包括了分支為路或圈的各種情況，旨在為今后研究Δ（G）≤3的情況作好準(zhǔn)備。

Δ（G）≤2的圖可以分為Δ（G）＝0、Δ（G）＝1、Δ（G）＝2這3類。下面，筆者分別討論這3類圖的Cor dial性。

1 Δ（G）＝0的圖的Cordial性

Δ（G）＝0表示圖G中所有的頂點(diǎn)都是孤立點(diǎn)。若圖G有2n個(gè)頂點(diǎn)，那么只需對(duì)其中n個(gè)標(biāo)0，另外n個(gè)標(biāo)1，則v0（G）＝v1（G）＝n，e0（G）＝e1（G）＝0，即得到圖G的一個(gè)Cordial標(biāo)號(hào)；若圖G有2n＋1個(gè)頂點(diǎn)，只需對(duì)其中n＋1個(gè)頂點(diǎn)標(biāo)0，另外n個(gè)標(biāo)1，則v0（G）－v1（G）＝1，e0（G）＝e1（G）＝0，即得到圖G的一個(gè)Cor dial標(biāo)號(hào)。因此，當(dāng)Δ（G）＝0時(shí)，圖G是Cor dial圖。

2 Δ（G）＝1的圖的Cor dial性

定義 符號(hào)D（i1，i2，…，ik）表示頂點(diǎn)度組成的集合為｛i1，i2，…，ik｝的一類圖。

Δ（G）＝1這樣的圖可以分為D（1）和D（1，0）。

引理1［4］設(shè)f是圖G的一個(gè)標(biāo)號(hào)。

1）若V0（G）中奇度點(diǎn)的數(shù)目為奇數(shù)，則e0（G）與e（G）的奇偶性相異；

2）若V0（G）中奇度點(diǎn)的數(shù)目為偶數(shù)，則e0（G）與e（G）的奇偶性相同。

D（1）是由P2構(gòu)成的圖類，當(dāng)G∈D（1）且e（G）＝4k＋2時(shí)，假設(shè)該圖G有Cor dial標(biāo)號(hào)，則v0（G）＝4k＋2為偶數(shù)，e0（G）＝2k＋1，與引理1矛盾，從而當(dāng)e（G）＝4k＋2時(shí)，G不是Cor dial圖；容易驗(yàn)證對(duì)于 ?G∈D（1），當(dāng)e（G）＝4k、e（G）＝4k＋1、e（G）＝4k＋3時(shí)，G是Cor dial圖。

D（1，0）是由P2和孤立點(diǎn)構(gòu)成的圖類，容易驗(yàn)證每個(gè)D（1，0）圖是Cor dial圖。

3 Δ（G）＝2的圖的Cor dial性

當(dāng)Δ（G）＝2時(shí)，這樣的圖又可以分為D（2）、D（2，0）、D（2，1）、D（2，1，0）4類。

3.1 D（2）

D（2）是由圈構(gòu)成的圖類，也稱二正則圖，由文獻(xiàn)［4］知，?G∈D（2）當(dāng)且僅當(dāng)時(shí)，G是Cordial圖。

3.2 D（2，0）

D（2，0）是由圈和孤立點(diǎn)構(gòu)成的圖類，則D（2，0）是偶度圖，由文獻(xiàn)［4］推論1知，當(dāng)G∈D（2，0）且e（G）≡2（mod4）時(shí)，G不是Cor dial圖；易驗(yàn)證對(duì)于?G∈D（2，0），當(dāng)e（G）≡0（mod4）、e（G）≡1（mod4）、e（G）≡3（mod4）時(shí)，G 是Cor dial圖。

3.3 D（2，1）

D（2，1）是由圈和路構(gòu)成的圖類，且至少有一個(gè)分支為路，但不能每個(gè)分支都是P2。

引理2 若圖G＊＝G1∪Ck是Cordial圖，則G＝G1∪Ck＋4也是Cordial圖。

證明 由文獻(xiàn)［4］中的引理2可得出結(jié)論。

引理3 若圖G＝G1∪Pk是Cor dial圖，則G＊＝G1∪Pk＋2也是Cor dial圖。

顯然：

從而：

即g是G＊的Cor dial標(biāo)號(hào)，從而G＊也是Cor dial圖。

由引理2、3知，欲證D（2，1）的圖G的Cor dial性，可假定G的分支都是C6，C5，C4，C3或P3，P2，并且至少有一個(gè)分支是P3或P2以及分支不能全是P2。

引理4 若圖G1有標(biāo)號(hào)f1，使得且G2是Cordial圖，則G＝G1∪G2是Cor dial圖。

證明 設(shè)G2有標(biāo)號(hào)f2，使得：

由于G＝G1∪G2，那么：

設(shè)：

首先把G2的頂點(diǎn)的0，1標(biāo)號(hào)互換，這不影響G1的標(biāo)號(hào)，且仍有e0（G2）＝e1（G2）＋1，只是v0（G2）＝v1（G2）＋1變成v0（G2）＝v1（G2）－1。于是：

從而G＝G1∪G2是Cordial圖。

證明 由于這些圖比較簡(jiǎn)單、具體，尋找滿足條件的標(biāo)號(hào)f很容易。僅以（8）和（11）為例給與證明。（8）中3個(gè)C3的頂點(diǎn)標(biāo)為（0，0，1），一個(gè)C3的頂點(diǎn)標(biāo)為（1，1，1），即得到滿足條件的標(biāo)號(hào)f；（11）中C6的頂點(diǎn)標(biāo)為（0，0，1，0，1，1），2個(gè)C5的頂點(diǎn)分別標(biāo)為（0，0，0，1，1），（1，1，1，0，0），則得到滿足條件的標(biāo)號(hào)f。

設(shè)G＝m1C6∪m2C5∪m3C3∪m4C4∪n1P3∪n2P2。由引理4及引理5的（1）（2）（3）（8）（9）（13）知，只需對(duì)情況m4＝n2＝0，m1∈｛0，1｝，｛m2，m3，n1｝?｛0，1，2，3｝，但m1，m2，m3，m4不同時(shí)為零，n1，n2不同時(shí)為零。又由（4）可假設(shè)m2，m3至少有一個(gè)為零，由（6）（7）可假設(shè)m2與n1及m3與n1至少一個(gè)為零。

圖G經(jīng)過(guò)以上約簡(jiǎn)后，會(huì)出現(xiàn)4種情況：

1）約簡(jiǎn)后的圖為空?qǐng)D。由引理4知，原來(lái)的圖G是Cor dial圖。

2）約簡(jiǎn)后的圖為2P2。因?yàn)镈（2，1）必有2度點(diǎn)，則在約簡(jiǎn)的過(guò)程中一定刪除了2C6或C4或C3∪C5、4C3、4C5、P3，那么可在約簡(jiǎn)的過(guò)程中保留一個(gè)刪減的分支，易驗(yàn)證2C6∪2P2、C4∪2P2、C3∪C5∪2P2、4C3∪2P2、4C5∪2P2、P3∪2P2都是Cordial圖。由引理4知，原來(lái)的圖G是Cordial圖。

3）約簡(jiǎn)后的圖為C6或2C3或2C5。因?yàn)镈（2，1）必有1度點(diǎn)，則在約簡(jiǎn)的過(guò)程中一定刪除了含有1度點(diǎn)的圖。當(dāng)約簡(jiǎn)后的圖是C6時(shí)，必刪除了4P2或P3或C5∪P2或C3∪P2，可以驗(yàn)證4P2∪C6、P3∪C6、C5∪P2∪C6、C3∪P2∪C6都是Cor dial圖；當(dāng)約簡(jiǎn)后的圖為2C3時(shí)，必刪除了4P2或P3或C3∪P2，易驗(yàn)證4P2∪2C3、P3∪2C3、C3∪P2∪2C3都是Cordial圖；當(dāng)約簡(jiǎn)后的圖為2C5時(shí)，必刪除了4P2或P3或C5∪P2，易驗(yàn)證4P2∪2C5、P3∪2C5、C5∪P2∪2C5都是Cor dial圖；由引理4知，原來(lái)的圖G是Cordial圖。

4）約簡(jiǎn)后的圖為C6∪P2或3C5或3C3或C5∪P3或C3∪P3，由于這些圖不在定理5中，所以在約簡(jiǎn)過(guò)程中不能被刪掉，但容易驗(yàn)證這些圖都是Cordial圖。由引理4知，原來(lái)的圖G是Cor dial圖。

由以上討論可以得到：每個(gè)D（2，1）圖都是Cor dial圖。

3.4 D（2，1，0）

D（2，1，0）是由D（2，1）中的圖和孤立點(diǎn)構(gòu)成的圖類。由每個(gè)D（2，1）圖都是Cor dial圖及Cordial圖添加孤立點(diǎn)后仍為Cor dial圖可得，每個(gè)D（2，1，0）圖也是Cor dial圖。

從以上討論可知，除了D（1）、D（2）和D（2，0）中邊數(shù)為4k＋2的圖外，其余的Δ（G）≤2的圖都是Cordial圖。

［1］Cahit R.Cordial graphs：A weaker version of gracef ul and har monious graphs ［J］.Ars Co mbinatoric，1987，23：201－208.

［2］Joseph A.Gallian，A Dyna mic Survey of Graph Labeling ［J］.The Electr onic Jour nal of co mbinatorics，2005，5：41－42.

［3］Cahit I.On Cor dial and 3－equit bale labeling of graphs ［J］.Utilitas Mat h，1990，37：189－198.

［4］徐麗平，劉峙山，倪臣敏 .二正則圖的Cordial性 ［J］.延邊大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，34（1）：21－22.

［5］陳麗娜，劉峙山 .一類圖的Cordial性 ［J］.數(shù)學(xué)研究，2007，40（4）：446－451.

［6］張升，堵根民 .圈輪的Cordial性 ［J］.內(nèi)蒙古師大學(xué)報(bào)自然科學(xué)（漢文）版，1999，28（4）：7－11.

［7］堵根民 .輪族的Cordial性問(wèn)題 ［J］.內(nèi)蒙古師大學(xué)報(bào)自然科學(xué)（漢文）版，2008，37（2）：180－184.