一種聯圖的Cordial性

倪臣敏，劉峙山，盧福良

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

一種聯圖的Cordial性

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

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

引入第一類圖G的概念，即若存在一個標號f，使得｜v0（G）－v1（G）｜≤1，e0（G）≥e1（G），則稱G為第一類圖.證明了第一類圖G與路P的聯圖G∨P，當P的階數大于等于G的最大度的2倍加2，即｜P｜≥2Δ（G）＋2時，都是Cordial圖，并進一步給出圖G是第一類圖的兩個充分條件.

第一類圖；路；聯；Cordial圖

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

1 相關定義

文中均為無向有限的簡單圖，標號為0－1標號.對于圖G的頂點集合V（G）的標號f，以f（u，v）＝｜f（u）－f（v）｜導出G的邊集合E（G）的標號.記

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

當同一圖G有更細的標號時，引入更細的標號，如用v0（f）＝v0（f；G），表示圖G中標號f為0的頂點集合的基數.

文中標i的頂點或者邊簡稱為i點或者i邊，其中i＝0，1.

定義1［11］設G和H是兩個不相交的圖，稱G∨H為G和H的聯圖.其中，V（G∨H）＝V（G）∪V（H），E（G∨H）＝E（G）∪E（H）∪｛uv｜u∈V（G），v∈V（H）｝.

定義2［1］如果對于圖G，存在一個標號f，使得

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

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

則稱G為Cordial圖，f是G的Cordial標號.

2 主要結果及其證明

引理1設f是圖G的一個標號，x∈V（G），g是僅把頂點x的f標號改變后得到的圖G的標號，則有

證明 因為d1（f；x）＝d0（f；x），又g與f導出的邊標號恰好只對于與頂點x關聯的邊不同，所以有

證畢.

引理2設f是圖G的一個標號，｛x，y｝?V（G），且f（x）≠f（y），g是僅對換x，y的f標號后得到的G的標號，則有v0（f）＝v0（g）且有

1）當xy?E（G）時，有

2）當xy∈E（G）時，有

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

1）對換x，y的標號相當于先改變x標號，再改變y的標號，由引理1可得，式（1）成立；

2）與1）的情況比較可得，改變x標號時，邊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存在一個標號f，使得

則稱G為第一類圖；否則，稱G為第二類圖.

引理3若G為第一類圖，則G或有標號h，使得

或有標號g，使得

證明 因G為第一類圖，故有標號f，使得

當e0（G）＝e1（G）時，f即引理的h，故可設e0（G）＞e1（G）.分兩種情況進行討論.

1）當｜G｜是奇數時，令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的標號，可得v0＝v1－1，由引理1知，e0（G）減少，但減少量不超過Δ（G）.若d0（z）≤d1（z），則存在某個i，使得d0（xi）＋d0（yi）－d1（xi）－d1（yi）＞0.對換xi，yi的標號，由引理2可知，e0（G）減少，且當xiyi?E（G）時，e0（G）的減少量為d0（xi）＋d0（yi）－d1（xi）－d1（yi）≤d0（xi）＋d0（yi）≤2Δ（G）；且當xiyi∈E（G）時，因xi，yi的標號不同，故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），可再繼續上面的步驟，直到出現e0（G）≤e1（G）為止.

令最后保持e0（G）＞e1（G）的標號為h，出現e0（G）≤e1（G）的標號為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）.在每對換一對頂點的標號時，e0（G）的減少量不超過2Δ（G），即e0（h；G）－e0（h；G）≤2Δ（G），從而易得引理3的兩個不等式.

對換xi，yi的標號并不影響G中0點和1點的數目，所以有

2）當｜G｜是偶數時，不出現上面的z，保留前面關于xi，yi的標號變化時的證明即可證.

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

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

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

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

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

證明 由題意可知，把G＊視為引理3中的G，因為G＊與P中頂點標號0，1可以獨立選擇，因此利用引理3，5的標號，使得｜v0（G）－v1（G）｜≤1.再有，對G的任意邊標號，均有e0（G）＋e1（G）＝e（G），故Cordial圖的邊標號條件｜e0（G）－e1（G）｜≤1等價于｜e0（G）－e（G）／2｜≤1／2.因為G＊是第一類圖，根據引理3可分如下兩種情況討論.

情形2G＊有標號g，使得e（G＊）／2－Δ（G＊）≤e0（g；G＊）≤e（G＊）／2.令e0（g；G＊）＝e（G＊）／2＋β，其中－Δ（G＊）≤β≤0.故只需選擇P的標號，使得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 第一類圖的充分條件及其證明

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

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

證明 1）給G一個標號f，使得f（xi）＝f（z）＝0，f（yi）＝1，i＝1，2，…，k.若e0（f；G）≥e1（f；G），則G即為第一類圖.

當d1（z）＞d0（z）＞0時，改變z的標號，e0（G）變大，則當某個i使得d1（xi）＋d1（yi）－d0（xi）－d0（yi）＞0時，由引理2的式（1）可知，對換xi，yi的標號，e0（G）增加.將此步驟進行若干次，必能得到一種標號，使得e0（G）≥e1（G）.命題得證.

2）證明方法與1）的方法類似，在此略過.

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

證明 考慮G的補圖ˉG，由已知條件知δ（G）≥｜G｜／2.由Dirac定理知，ˉG有Hamilton圈H，在H中相鄰的每對頂點在G中不相鄰，故G滿足定理2的條件，從而G為第一類圖.

若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］ 倪臣敏，劉峙山，陳麗娜.關于一點聯的Cordial性的一個結果的推廣［J］.延邊大學學報：自然科學版，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］ 劉群，劉峙山.最大邊數的Cordial圖的構造［J］.數學研究，2003，36（4）：437－439.

［8］ 劉峙山，堵根民.三正則連通圖的Cordial性［J］.數學研究，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

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

1000－5013（2014）01－0117－04

10.11830／ISSN.1000－5013.2014.01.0117

2012－12－19

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

國家自然科學基金資助項目（11226288）