倪臣敏，劉峙山，盧福良

（1.華僑大學(xué)廈門(mén)工學(xué)院高等數(shù)學(xué)教學(xué)系，福建廈門(mén)361021；2.仰恩大學(xué)數(shù)學(xué)系，福建泉州362014；3.臨沂大學(xué)數(shù)學(xué)系，山東臨沂276005）

一種聯(lián)圖的Cordial性

倪臣敏1，劉峙山2，盧福良3

（1.華僑大學(xué)廈門(mén)工學(xué)院高等數(shù)學(xué)教學(xué)系，福建廈門(mén)361021；2.仰恩大學(xué)數(shù)學(xué)系，福建泉州362014；3.臨沂大學(xué)數(shù)學(xué)系，山東臨沂276005）

引入第一類(lèi)圖G的概念，即若存在一個(gè)標(biāo)號(hào)f，使得｜v0（G）－v1（G）｜≤1，e0（G）≥e1（G），則稱(chēng)G為第一類(lèi)圖.證明了第一類(lèi)圖G與路P的聯(lián)圖G∨P，當(dāng)P的階數(shù)大于等于G的最大度的2倍加2，即｜P｜≥2Δ（G）＋2時(shí)，都是Cordial圖，并進(jìn)一步給出圖G是第一類(lèi)圖的兩個(gè)充分條件.

第一類(lèi)圖；路；聯(lián)；Cordial圖

自1987年Cahit提出Cordial圖的概念［1］至今，各種圖的Cordial性的研究不斷出現(xiàn)［110］，如有關(guān)聯(lián)圖的Cordial性的結(jié)果研究［2－5］.Cm∨Kn，mCn，Pm∨Kn，Pm∨K1，n的Cordial性已在一定條件下得到解決，但Cm，Kn，Pm，Kn都是十分具體的，簡(jiǎn)單的圖.文獻(xiàn)［3］研究由G導(dǎo)出的圖Pt（G）（即把G的所有邊都用長(zhǎng)為t的路來(lái)代替后得到的新圖）的Cordial性，但有關(guān)結(jié)論都是在G是Cordial圖的前提條件下給出的；文獻(xiàn)［4］給出了Pt（K2n），Pt（K2n＋1）的Cordial性證明結(jié)論.但有關(guān)聯(lián)圖G∨P的Cordial性均未作深入的研究.本文引入了第一類(lèi)圖的概念，證明了這類(lèi)圖中的任意一個(gè)圖G，只要路P的階數(shù)｜P｜≥2Δ（G）＋2，G∨P就是Cordial圖.

1 相關(guān)定義

文中均為無(wú)向有限的簡(jiǎn)單圖，標(biāo)號(hào)為0－1標(biāo)號(hào).對(duì)于圖G的頂點(diǎn)集合V（G）的標(biāo)號(hào)f，以f（u，v）＝｜f（u）－f（v）｜導(dǎo)出G的邊集合E（G）的標(biāo)號(hào).記

并以v0，v1，e0，e1分別表示它們的基數(shù).

當(dāng)同一圖G有更細(xì)的標(biāo)號(hào)時(shí)，引入更細(xì)的標(biāo)號(hào)，如用v0（f）＝v0（f；G），表示圖G中標(biāo)號(hào)f為0的頂點(diǎn)集合的基數(shù).

文中標(biāo)i的頂點(diǎn)或者邊簡(jiǎn)稱(chēng)為i點(diǎn)或者i邊，其中i＝0，1.

定義1［11］設(shè)G和H是兩個(gè)不相交的圖，稱(chēng)G∨H為G和H的聯(lián)圖.其中，V（G∨H）＝V（G）∪V（H），E（G∨H）＝E（G）∪E（H）∪｛uv｜u∈V（G），v∈V（H）｝.

定義2［1］如果對(duì)于圖G，存在一個(gè)標(biāo)號(hào)f，使得

1）｜v0（G）－v1（G）｜≤1；

2）｜e0（G）－e1（G）｜≤1.

則稱(chēng)G為Cordial圖，f是G的Cordial標(biāo)號(hào).

2 主要結(jié)果及其證明

引理1設(shè)f是圖G的一個(gè)標(biāo)號(hào)，x∈V（G），g是僅把頂點(diǎn)x的f標(biāo)號(hào)改變后得到的圖G的標(biāo)號(hào)，則有

證明 因?yàn)閐1（f；x）＝d0（f；x），又g與f導(dǎo)出的邊標(biāo)號(hào)恰好只對(duì)于與頂點(diǎn)x關(guān)聯(lián)的邊不同，所以有

證畢.

引理2設(shè)f是圖G的一個(gè)標(biāo)號(hào)，｛x，y｝?V（G），且f（x）≠f（y），g是僅對(duì)換x，y的f標(biāo)號(hào)后得到的G的標(biāo)號(hào)，則有v0（f）＝v0（g）且有

1）當(dāng)xy?E（G）時(shí)，有

2）當(dāng)xy∈E（G）時(shí)，有

證明 由G的定義可知，顯然有v0（f）＝v0（g），則

1）對(duì)換x，y的標(biāo)號(hào)相當(dāng)于先改變x標(biāo)號(hào)，再改變y的標(biāo)號(hào)，由引理1可得，式（1）成立；

2）與1）的情況比較可得，改變x標(biāo)號(hào)時(shí)，邊xy由1邊變成0邊，故式（2）中的d1（f；y）比式（1）中的d1（f；y）少1，而式（2）中的d0（f；y）比式（1）中的d0（f；y）大1.因此，式（2）的右端比式（1）的右端少2，故可得等式（2）.

定義3若圖G存在一個(gè)標(biāo)號(hào)f，使得

則稱(chēng)G為第一類(lèi)圖；否則，稱(chēng)G為第二類(lèi)圖.

引理3若G為第一類(lèi)圖，則G或有標(biāo)號(hào)h，使得

或有標(biāo)號(hào)g，使得

證明 因G為第一類(lèi)圖，故有標(biāo)號(hào)f，使得

當(dāng)e0（G）＝e1（G）時(shí)，f即引理的h，故可設(shè)e0（G）＞e1（G）.分兩種情況進(jìn)行討論.

1）當(dāng)｜G｜是奇數(shù)時(shí)，令V（G）＝｛x1，x2，…，xl；y1，y2，…，yl；z｝，f（xi）＝f（z）＝0，f（yi）＝1，i＝1，…，l，則有

若d0（z）＞d1（z），改變z的標(biāo)號(hào)，可得v0＝v1－1，由引理1知，e0（G）減少，但減少量不超過(guò)Δ（G）.若d0（z）≤d1（z），則存在某個(gè)i，使得d0（xi）＋d0（yi）－d1（xi）－d1（yi）＞0.對(duì)換xi，yi的標(biāo)號(hào)，由引理2可知，e0（G）減少，且當(dāng)xiyi?E（G）時(shí)，e0（G）的減少量為d0（xi）＋d0（yi）－d1（xi）－d1（yi）≤d0（xi）＋d0（yi）≤2Δ（G）；且當(dāng)xiyi∈E（G）時(shí)，因xi，yi的標(biāo)號(hào)不同，故d1（xi）≥1，d1（yi）≥1，d1（xi）＋d1（yi）≥2.由引理2可知：e0（G）的減少量為d0（xi）＋d0（yi）＋2－d1（xi）－d1（yi）≤d0（xi）＋d0（yi）≤2Δ（G）；若e0（G）變小后，仍有e0（G）＞e1（G），可再繼續(xù)上面的步驟，直到出現(xiàn)e0（G）≤e1（G）為止.

令最后保持e0（G）＞e1（G）的標(biāo)號(hào)為h，出現(xiàn)e0（G）≤e1（G）的標(biāo)號(hào)為g，則有e0（h；G）＞e1（h；G），e0（g；G）≤e1（g；G）.因e0（G）＋e1（G）＝e（G），故有e1（g；G）≤e（G）／2＜e0（h；G）.在每對(duì)換一對(duì)頂點(diǎn)的標(biāo)號(hào)時(shí)，e0（G）的減少量不超過(guò)2Δ（G），即e0（h；G）－e0（h；G）≤2Δ（G），從而易得引理3的兩個(gè)不等式.

對(duì)換xi，yi的標(biāo)號(hào)并不影響G中0點(diǎn)和1點(diǎn)的數(shù)目，所以有

2）當(dāng)｜G｜是偶數(shù)時(shí)，不出現(xiàn)上面的z，保留前面關(guān)于xi，yi的標(biāo)號(hào)變化時(shí)的證明即可證.

引理4設(shè)f是n階路P＝Pu1，…，un的一個(gè)標(biāo)號(hào)（其中n≥4），｜E0，0（P）｜＞0，｜E1，1（P）｜＞0，則P存在另一標(biāo)號(hào)g，滿(mǎn)足v0（g）＝v1（f），e0（g）＝e1（f）－2.

證明 不妨設(shè)f（ui）＝f（ui＋1）＝0，f（uj）＝f（uj＋1）＝1，其中i＋1＜j，i＝1，2，…，n－3，并設(shè)ui＋1與uj之間無(wú)0邊.那么，必有f（ui＋2）＝1，f（ui＋3）＝0，f（ui＋4）＝1，…，f（uj－1）＝0.

對(duì)換ui＋1與ui＋2的標(biāo)號(hào)，v0（P）和e0（P）并不改變，但是新的0邊ui＋2ui＋3與0邊ujuj＋1的距離變小.用此方法變換直到uj－2uj－1的標(biāo)號(hào)為0，此時(shí)，再對(duì)換uj－1和uj的標(biāo)號(hào)，即得所需標(biāo)號(hào)g.

引理5對(duì)于任意的n階路P＝Pu1，…，un（其中n≥3）及K＝｛0，1，2，…，n－2｝，都存在標(biāo)號(hào)f，使得

定理1若G＊為第一類(lèi)圖，G＝G＊∨P，｜P｜≥2Δ（G）＋2，則G是Cordial圖.

證明 由題意可知，把G＊視為引理3中的G，因?yàn)镚＊與P中頂點(diǎn)標(biāo)號(hào)0，1可以獨(dú)立選擇，因此利用引理3，5的標(biāo)號(hào)，使得｜v0（G）－v1（G）｜≤1.再有，對(duì)G的任意邊標(biāo)號(hào)，均有e0（G）＋e1（G）＝e（G），故Cordial圖的邊標(biāo)號(hào)條件｜e0（G）－e1（G）｜≤1等價(jià)于｜e0（G）－e（G）／2｜≤1／2.因?yàn)镚＊是第一類(lèi)圖，根據(jù)引理3可分如下兩種情況討論.

情形2G＊有標(biāo)號(hào)g，使得e（G＊）／2－Δ（G＊）≤e0（g；G＊）≤e（G＊）／2.令e0（g；G＊）＝e（G＊）／2＋β，其中－Δ（G＊）≤β≤0.故只需選擇P的標(biāo)號(hào)，使得e0（P）－e（P）／2取值－β或－β±1／2即可.由于有｜P｜－2－（｜P｜－1）／2＝（｜P｜－3）／2≥Δ（G＊）－1／2≥－β－1／2，故e0（P）－e（P）／2必然可以取到－β或－β±1／2.

3 第一類(lèi)圖的充分條件及其證明

定理21）若奇階圖G的V（G）＝｛x1，x2，…，xk，y1，y2，…，yk，z｝滿(mǎn)足xiyi?E（G），i＝1，2，…，k，則G為第一類(lèi)圖.

2）若偶階圖G的V（G）＝｛x1，x2，…，xk，y1，y2，…，yk｝滿(mǎn)足xiyi?E（G），i＝1，2，…，k，則G為第一類(lèi)圖.

證明 1）給G一個(gè)標(biāo)號(hào)f，使得f（xi）＝f（z）＝0，f（yi）＝1，i＝1，2，…，k.若e0（f；G）≥e1（f；G），則G即為第一類(lèi)圖.

當(dāng)d1（z）＞d0（z）＞0時(shí)，改變z的標(biāo)號(hào)，e0（G）變大，則當(dāng)某個(gè)i使得d1（xi）＋d1（yi）－d0（xi）－d0（yi）＞0時(shí)，由引理2的式（1）可知，對(duì)換xi，yi的標(biāo)號(hào)，e0（G）增加.將此步驟進(jìn)行若干次，必能得到一種標(biāo)號(hào)，使得e0（G）≥e1（G）.命題得證.

2）證明方法與1）的方法類(lèi)似，在此略過(guò).

定理3如果Δ（G）≤｜G｜／2－1，則G為第一類(lèi)圖.

證明 考慮G的補(bǔ)圖ˉG，由已知條件知δ（G）≥｜G｜／2.由Dirac定理知，ˉG有Hamilton圈H，在H中相鄰的每對(duì)頂點(diǎn)在G中不相鄰，故G滿(mǎn)足定理2的條件，從而G為第一類(lèi)圖.

若e0（f；G）＜e1（f；G），則有

［1］ CAHIT I.Cordial graghs：A weak version of graceful and harmonious graphs［J］.Ars Combin，1987（23）：201－208.

［2］ JOSEPH A G.A dynamic survey of graph labeling［J］.Electronic Journal of Combinatorics，2009（16）：49－53.

［3］ ANDAR M，BOXWALA S，LIMAYE N B.On the cordiality of the t－uniform homeomorphs－I［J］.Ars Combin，2003（66）：313－318.

［4］ ANDAR M，BOXWALA S，LIMAYE N B.On the cordiality of the t－uniform homeomorphs－II［J］.Ars Combin，2003（67）：213－220.

［5］ 倪臣敏，劉峙山，陳麗娜.關(guān)于一點(diǎn)聯(lián)的Cordial性的一個(gè)結(jié)果的推廣［J］.延邊大學(xué)學(xué)報(bào)：自然科學(xué)版，2007，33（2）：94－97.

［6］ XIE Yan－tao，CHE Ying－tao，LIU Zhi－shan.The cordiality on the union of 3－regular connected graph and cycle［J］.Chinese Quarterly Journal of Mathematics，2010，25（2）：244－248.

［7］ 劉群，劉峙山.最大邊數(shù)的Cordial圖的構(gòu)造［J］.數(shù)學(xué)研究，2003，36（4）：437－439.

［8］ 劉峙山，堵根民.三正則連通圖的Cordial性［J］.數(shù)學(xué)研究，2007，40（1）：114－116.

［9］ GHEBLEH M，KHOEILAR R.A note on“H－cordial graphs”［J］.Bull Inst Combin Appl，2001（31）：60－68.

［10］ KIRCHHERR W W.NEPS operations on cordial graphs［J］.Discrete Math，1993（115）：201－209.

［11］ BONDY J A，MURTY U S R.Graph theory with applications［M］.New York：American Elsevier，1976：117－118.

On the Cordiality of a Union of Graphs

NI Chen－min1，LIU Zhi－shan2，LU Fu－liang3
（1.Teaching Department of High Mathematics of Institue of Technology，Huaqiao University，Xiamen 361021，China；2.Department of Mathematics，Yangen Universiyty，Quanzhou 362014，China；3.Department of Mathematics，Linyi Universiyty，Linyi 276005，China）

The first class of graphs is introduced.If a graph has a lebaling f，s.t.｜v0（G）－v1（G）｜≤1，e0（G）≥e1（G），it is called to be the first class of graphs.Let Gbe a graph of this class and Pbe a path with｜P｜≥2Δ（G）＋2，it is proved that G∨Pis a Cordial graph，and two sufficient conditions are given to make Gto be the first class of graphs.

the first class of graphs；path；union；cordial graph

O 157.5

A

（責(zé)任編輯：陳志賢 英文審校：黃心中）

1000－5013（2014）01－0117－04

10.11830／ISSN.1000－5013.2014.01.0117

2012－12－19

倪臣敏（1980－），女，講師，主要從事圖論與組合學(xué)，圖像處理與分析的研究.E－mail：cmni＠163.com.

國(guó)家自然科學(xué)基金資助項(xiàng)目（11226288）