D(0，3)圖的Cordial 性①

倪臣敏，劉峙山，盧福良

(1.廈門工學(xué)院 高等數(shù)學(xué)教學(xué)系，福建 廈門361021;2.呼和浩特職業(yè)學(xué)院，內(nèi)蒙古 呼和浩特010000;3.臨沂大學(xué) 數(shù)學(xué)系，山東 臨沂276000)

0 引 言

圖的標(biāo)號(hào)問題源于60 年代中期G.Ringel［1］和A.Rosa［2］提出的優(yōu)美樹的猜想，現(xiàn)已成為一個(gè)重要而活躍的研究分支［6～13］.相關(guān)的結(jié)果被廣泛應(yīng)用于射電天文學(xué)、X－射線衍射晶體學(xué)、密碼設(shè)計(jì)、導(dǎo)彈控制碼設(shè)計(jì)、同步機(jī)碼設(shè)計(jì)等領(lǐng)域［3～4］.Cordial 標(biāo)號(hào)是優(yōu)美標(biāo)號(hào)及調(diào)和標(biāo)號(hào)的一種弱化，其研究始于1987 年Cahit 的一篇論文［5～6］，在這篇論文中，Cahit 明確給出了Cordial 圖的定義.在文獻(xiàn)［7］中，Seoud 和Abdel Maqusoud 證明了奇度圖是Cordial 圖的充分條件為;在文獻(xiàn)［8］中，完善了Seoud 和Abdel Maqusoud 的結(jié)論，證明了D(1，3)圖是Cordial 圖的充要條件為;在文獻(xiàn)［9］中，作者證明了3 正則圖是Cordial 圖的充要條件為4.在本文中，將討論D(0，3)圖的Cordial 性，并證明了所有的D(0，3)圖都是Cordial 圖.

本文論及的都是無向有限的簡(jiǎn)單圖，標(biāo)號(hào)均為0－1 標(biāo)號(hào).對(duì)于圖G 的頂點(diǎn)集合V(G)的標(biāo)號(hào)f，以導(dǎo)出G 的邊集合E(G)的標(biāo)號(hào).以Vi=Vi(G)={v|v ∈V(G)，f(v)=i}表示所有的頂點(diǎn)標(biāo)號(hào)為i 的點(diǎn)構(gòu)成的集合，以Ei=Ei(G)={uv|u，v ∈V(G)，f(uv)=i}表示所有的標(biāo)號(hào)為i 的邊構(gòu)成的集合，i=0，1.記i，f(v)=j，或f(u)=j，f(v)=i}，{i，j}={0，1}，E0=E00∪E11，E1=E01∪E10，并以v0，v1，e0，e1分別表示它們的基數(shù).當(dāng)同一圖G 有更細(xì)的標(biāo)號(hào)時(shí)，引入更細(xì)的記號(hào)，如用v0(f)=v0(f:G)=v0(G)表示圖G 中標(biāo)號(hào)f 為0 的頂點(diǎn)集合的基數(shù)，用e0(f)=e0(f:G)=e0(G)表示圖G 中標(biāo)號(hào)f 為0 的邊集合的基數(shù).文中標(biāo)i 的頂點(diǎn)或者邊簡(jiǎn)稱為i 點(diǎn)或者i 邊，其中i=0，1.其它相關(guān)專業(yè)術(shù)語(yǔ)可詳見文獻(xiàn)［12］.

定義1［6］若圖G 存在一個(gè)0－1 標(biāo)號(hào)f 滿足:(1)|v0(G)－v1(G)|≤1;(2)|e0(G)－e1(G)|≤1，則稱f 是G 的Cordial 標(biāo)號(hào)，稱G 為Cordial 圖.

定義2 設(shè)dG(x)(或簡(jiǎn)寫為d(x))為圖G 中頂點(diǎn)x 的度，若對(duì)于任意x ∈V(G)，dG(x)∈{i1，…，ik}，k ∈N 則稱圖G 為D(i1，…，ik)圖.

定義3［10］對(duì)于圖G，若存在一個(gè)Cordial 標(biāo)號(hào)f，使得v0(f:G)=v1(f:G)，e0(f:G)=e1(f:G)，則稱G 為嚴(yán)格Cordial 圖.

1 主要內(nèi)容

引理1 設(shè)G=A ∪B，其中B 為由孤立點(diǎn)構(gòu)成的圖.若A 為Cordial 圖，則G 為Cordial 圖.

證明: 顯然，G 中的邊即為圖A 的邊.設(shè)f 是圖A 的Cordial 標(biāo)號(hào)，在G 中保持f 在A 中的頂點(diǎn)標(biāo)號(hào)不變，則G 中A 的邊標(biāo)號(hào)不變;調(diào)整B 中的頂點(diǎn)標(biāo)號(hào)，容易獲得滿足定義1 的Cordial 標(biāo)號(hào)，故G 為Cordial 圖.

引理2 在一個(gè)圖中增加或者減少一個(gè)嚴(yán)格Cordial 圖的分支，不改變圖的Cordial 性

此證明略，讀者可自行推導(dǎo).

定理1 設(shè)G 為D(0，3)圖，且每個(gè)分支的階不大于4，則G 為Cordial 圖.

證明: 由題意，G 的每個(gè)分支或者為孤立點(diǎn)，或者為4 階3－正則圖.容易驗(yàn)證兩個(gè)4 階3－正則圖的并為嚴(yán)格Cordial 圖，依次從G 中去除一對(duì)一對(duì)的4 階3－正則圖，設(shè)最后G 被化簡(jiǎn)成的圖為M，則M 有兩種情況.

情況1，M 由孤立點(diǎn)構(gòu)成，則M 為Cordial 圖，由引理2，G 為Cordial 圖.

情況2，M 由一個(gè)4 階3－正則圖和孤立點(diǎn)構(gòu)成.給此3－正則圖如圖1 的標(biāo)號(hào)，若孤立點(diǎn)的個(gè)數(shù)為奇數(shù)個(gè)，則將孤立點(diǎn)標(biāo)n+1 個(gè)0，n 個(gè)1，此時(shí)|v0(M)－v1(M)|=|n+1+1－(n+3)|≤1;|e0(M)－e1(M)|=0 ≤1，故M 為Cordial 圖，由引理2，G 為Cordial 圖;若孤立點(diǎn)的個(gè)數(shù)為偶數(shù)個(gè)，則將孤立點(diǎn)標(biāo)n+1 個(gè)0，n－1 個(gè)1，同理可得，M 為Cordial 圖，從而G 為Cordial 圖.

圖1 定理1 中情況2 的3－正則圖標(biāo)號(hào)

圖2 解釋引理4

引理3 對(duì)于有最大度ΔG=Δ 的圖G，存在標(biāo)號(hào)f，使得|v0(G)－v1(G)|≤1，|e0(G)－e1(G)|≤2Δ，且有如下結(jié)論:

(i)當(dāng)e0(G)－e1(G)=2Δ 時(shí)，存在{x，y}?V(G)，使得{f(x)，f(y)}={0，1}，d(x)=d(y)=Δ，且頂點(diǎn)x，y 的標(biāo)號(hào)分別與它們的鄰點(diǎn)標(biāo)號(hào)相同;

(ii)當(dāng)e0(G)－e1(G)=－2Δ 時(shí)，存在{x，y}?V(G)，使得{f(x)，f(y)}= {0，1}，d(x)=d(y)=Δ，且頂點(diǎn)x，y 的標(biāo)號(hào)分別與它們的鄰點(diǎn)標(biāo)號(hào)不同.

證明: 設(shè)C ?V(G)，{x，y}?V(G)－C，且xy ?E(G)，f 是C 的一個(gè)標(biāo)號(hào)，當(dāng)V(G)－C 沒有標(biāo)號(hào)時(shí)，約定Vi(G)=Vi(C)，ei(G)=ei(G［C］).設(shè)x 在C 中的鄰點(diǎn)有q 個(gè)標(biāo)0，r 個(gè)標(biāo)1，y 在C 中的鄰點(diǎn)有s 個(gè)標(biāo)0，t 個(gè)標(biāo)1.那么，當(dāng)令f(x)=0，f(y)=1 時(shí)，e0－e1的增量是q+t－r－s;當(dāng)令f(x)=1，f(y)=0 時(shí)，e0－e1的增量是r+s－(q+t)，這兩個(gè)增加量總有一個(gè)非負(fù)，也總有一個(gè)非正.現(xiàn)規(guī)定，當(dāng)e0(G［C］)－e1(G［C］)≤0 時(shí)，給{x，y}標(biāo)號(hào)使得e0－e1的增量非負(fù);當(dāng)e0(G［C］)－e1(G［C］)＞0 時(shí)，給{x，y}標(biāo)號(hào)使得e0－e1的增量非正.由于q+t ≤d(x)+d(y)≤2Δ，同理r+s ≤2Δ，因此若原來的－2Δ ＜e0(G［C］)－e1(G［C］)≤2Δ，總是可以定義{x，y}的標(biāo)號(hào)，使得{f(x)，f(y)}={0，1}，－2Δ ＜e0(G［C ∪{x，y}］)－e1(G［C ∪{x，y}］)≤2Δ.進(jìn)一步看出，若原來e0(G［C］)－e1(G［C］)＜2Δ，而e0(G［C ∪{x，y}］)－e1(G［C∪{x，y}］)=2Δ，必然是e0－e1的增量為正，即原來e0(G［C］)－e1(G［C］)≤0，如此，增加量e0－e1≥2Δ.因最大度為Δ，故此時(shí)必然是原來的e0(G［C］)－e1(G［C］)=0，且d(x)=d(y)=Δ，且頂點(diǎn)x，y 的標(biāo)號(hào)分別與它們的鄰點(diǎn)標(biāo)號(hào)相同.結(jié)論(i)得證，同理可得結(jié)論(ii).

下面，在V(G)中挑選出不相鄰的點(diǎn)對(duì)xi，yi，直到選不出這樣的點(diǎn)對(duì)為止.剩下的沒有不相鄰的點(diǎn)必構(gòu)成完全圖Km，因?yàn)棣?G)=Δ，所以m ≤Δ+1.給Km的頂點(diǎn)標(biāo)號(hào)，使得|v0(Km)－v1(Km)|≤1，此時(shí)2Δ.設(shè)取出的不相鄰點(diǎn)對(duì)為x1，y1;…;xk，yk，依照開始的規(guī)則和分析，逐次給以上點(diǎn)對(duì)標(biāo)號(hào)，即可得引理3 的結(jié)論.

引理4 設(shè)G 為D(0，3)圖，且G 中有一個(gè)分支Gk(|Gk|≥6)，則存在C={x，y，z，u，v，w}?V(Gk)，使得{xy，yz，yv，uv，vw}?E(G［C］)，其中u 和z 或者x 和w 可能重合.

證明:(i)若Gk中含K4－e，首先給K4－e 如圖2(1)的標(biāo)號(hào)(頂點(diǎn)u 與z 重合)，設(shè)w ∈N(v)－{u，y}，∵，∴，設(shè)N(w)={v，w1，w2}，則w1，w2至多有一個(gè)與x 重合，如圖2(1);

(ii)若Gk中含C3但不含K4－e，設(shè)C3的三個(gè)頂點(diǎn)為y，z，v，v 在C3以外的各鄰點(diǎn)為x，z′，u，因Gk中不包含K4－e，故x，z′，u 任意兩點(diǎn)不重合，如圖2(2);

(iii)若Gk中不含C3，任取其兩相鄰頂點(diǎn)記為y，v，設(shè)N(y)={x，z，v}，N(v)={y，u，w}，因Gk中不含C3，故x，u，z，w 任意兩點(diǎn)不重合，如圖2(3).

由(i)(ii)(iii)，命題得證.

定理2 所有的D(0，3)圖均為Cordial 圖.

證明:(i).若G 為D(0，3)圖，則G=A ∪B，其中A 為3－正則圖，B 為由孤立點(diǎn)構(gòu)成的圖.根據(jù)文獻(xiàn)［9］，當(dāng)時(shí)，A 為Cordial 圖，由引理1，G 為Cordial 圖.

(ii).當(dāng)A 不是Cordial 圖，即|A|=8n+4，則，且由［11］知，e0(A)為偶數(shù)，故e0(A)－e1(A)≡2(mod 4).若A 的每個(gè)分支的階都不大于4，由定理1 可得結(jié)論;否則，若A 中含K4，則A=K4∪H，其中H 為8n 階3－正則圖，由［3 ～4］，H 為嚴(yán)格Cordial 圖，且容易驗(yàn)證K4∪K1是Cordial 圖，故A∪K1=K4∪H ∪K1為Cordial 圖，由引理1，G=A ∪B 為Cordial 圖.接下來討論A 中不含K4的情況，此時(shí)G 的每個(gè)分支Gk的階數(shù)至少為6.

根據(jù)引理3，在圖A 上存在標(biāo)號(hào)f，使得|v0(A)－v1(A)|≤1，|e0(A)－e1(A)|≤2Δ=6，因?yàn)閨A|=8n+4，故此時(shí)必有v0(f;A)=v1(f:A).因e0(A)－e1(A)≡2(mod 4)，故此時(shí)e0(f:A)－e1(f:A)∈{±2，±6}.當(dāng)e0(A)－e1(A)=－6=－2Δ 時(shí)，由引理3(ii)A 中必存在標(biāo)號(hào)如圖3(1)(2)的3 度點(diǎn)，把A ∪{p}中的孤立點(diǎn)p 標(biāo)號(hào)為0，把圖3(1)中的三度點(diǎn)x 改標(biāo)號(hào)為1，則圖A ∪{p}獲得標(biāo)號(hào)，使得

圖3 e0(A)－e1(A)=±6 時(shí)，A 中存在的頂點(diǎn)標(biāo)號(hào)

或者把圖3(2)中的三度點(diǎn)y 改標(biāo)號(hào)為0，把A∪{p}中的孤立點(diǎn)p 標(biāo)號(hào)為1，則圖A ∪{p}獲得標(biāo)號(hào)，使得

當(dāng)e0(A)－e1(A)=6 時(shí)，由引理3(i)A 中必有標(biāo)號(hào)如圖3(3)(4)的3 度點(diǎn)，把A ∪{p}中的孤立點(diǎn)p 標(biāo)號(hào)為0，把圖3(3)中的三度點(diǎn)a 標(biāo)號(hào)為1，則圖A ∪{p}獲得標(biāo)號(hào)，使得

或者把圖3(4)中的三度點(diǎn)b 標(biāo)號(hào)為0，把A ∪{p}中的孤立點(diǎn)p 標(biāo)號(hào)為1，則圖A ∪{p}獲得標(biāo)號(hào)，使得

當(dāng)e0(A)－e1(A)=±2 時(shí)，因|Gk|≥6，由引理4，A 中存在形如圖2 的子圖(其中u，z 或者x，w可能重合)，給C={x，y，z，u，v，w}標(biāo)號(hào)為令f(y)=f(v)=0，然后在G［{x，z，u，w}］中選度最小的頂點(diǎn)x 標(biāo)0，其他3 個(gè)頂點(diǎn)標(biāo)1.

當(dāng)e0(A)－e1(A)=－2 時(shí)，令f(v)=1，并把A ∪{p}中的孤立點(diǎn)p 標(biāo)號(hào)為0，則

當(dāng)e0(A)－e1(A)=2 時(shí)，令f(y)=1，并把A∪{p}中的孤立點(diǎn)p 標(biāo)號(hào)為0，則.

綜上所述，當(dāng)e0(A)－e1(A)=±6 和±2 時(shí)，

即A ∪{p}是Cordial 圖，由引理1，G=A ∪B=A ∪{p}或者G=A ∪B=A ∪{p}∪{其它孤立點(diǎn)}是Cordial 圖.定理得證.

［1］ Ringel.G.，Problem 25，in:Theory of Graphs and Its Applications［C］.Proc Symposium Smo－ lenice Prague，1963:162－167.

［2］ Rosa.A.On Certain Valuations of the Vertices of a Graph［C］.Theory of Graphs，1966，(7):349－355.

［3］ G.S.Bloom and S.W.Golomb，Numbered Complete Graphs，Unusual Rulers，and Assorted Applications，Theory and Applications of Graphs［M］.Springer－Verlag，NewYork，1978，(642):53－65.

［4］ M.Sutton，Summable Graphs Labelings and their Applications.(Ph.D.Thesis)［D］.Dcpt.Computer Science，The University of Newcastle，2001.

［5］ Joseph A.Gallian，A Dynamic Survey of Graph Labeling，the Electronic Journal of Combinatorics［J］.2012，(19):51－58.

［6］ Cahit I.Cordial graph:A Weak Version of Graceful and Harmonious Graphs，Ars Combin［J］.1987，(23):201－207.

［7］ M.A.Seoud and A.E.I.Abdel Maqsoud，On Cordial and Balanced Labelings of Graphs［J］.Egyptian Math.Soc，1999，(7):27－135.

［8］ Ni Chenmin，Liu Zhishan，On the Cordiality of Graphs，Ars Combin［J］.2014，(113):451－455.

［9］ Liu Zhishan，Zhu Biwen，A Necessary and Sufficient Condition for A 3－Regular Graph to be Cordial.Ars Combin［J］.2007，(84):225－230.

［10］ 徐麗平，劉峙山，倪臣敏，2－正則圖的Cordial 性，延邊大學(xué)學(xué)報(bào)(自然科學(xué)版)［J］.2008，(03):21－22.

［11］ 劉峙山，堵根民，三正則連通圖的Cordial 性，數(shù)學(xué)研究，2007，(03):114－116.

［12］ Bondy J.A.and Murty U.S.R.，Graph Theory with Applications［M］.New York:American Elsevier，1976.