圖2×Cn的平衡性和符號(hào)邊控制數(shù)

童細(xì)心

（汕頭職業(yè)技術(shù)學(xué)院 自然科學(xué)系，廣東 汕頭 515041）

圖2×Cn的平衡性和符號(hào)邊控制數(shù)

童細(xì)心

（汕頭職業(yè)技術(shù)學(xué)院 自然科學(xué)系，廣東 汕頭 515041）

文章證明了圖2×Cn在n=4k時(shí)是平衡圖，給出了其平衡特征，并確定了圖的符號(hào)邊控制數(shù).

圖2×Cn；平衡圖；符號(hào)邊控制函數(shù)；符號(hào)邊控制數(shù)

1 引言與預(yù)備知識(shí)

圖的控制理論是圖論中一個(gè)十分重要的內(nèi)容，其研究?jī)?nèi)容也越來(lái)越廣泛［1］.本文研究了一類(lèi)圖的平衡標(biāo)號(hào)及其符號(hào)邊控制數(shù).設(shè)G=（V，E）為一個(gè)無(wú)向簡(jiǎn)單圖，對(duì)任意e∈E，用NG（e）表示G中與e相鄰的邊集，NG［e］= NG（e）∪｛e｝為e的閉邊鄰域，在不引起混淆的情況下，簡(jiǎn)記為N（e）和N［e］.其他未加說(shuō)明的定義和符號(hào)均來(lái)自文獻(xiàn)［2］.

定義1［3］對(duì)于簡(jiǎn)單圖G=（V，E），若?v∈V，存在單射，且導(dǎo)出的邊標(biāo)號(hào)的雙射，則稱(chēng)圖G是優(yōu)美圖，稱(chēng)L為圖G的優(yōu)美標(biāo)號(hào).

定義2［3］設(shè)L為G的一個(gè)優(yōu)美標(biāo)號(hào)，若存在正整數(shù)λ，使得對(duì)任意，都有L（u）≤λ＜L（v）或L（v）≤成立，則稱(chēng)L為G的平衡標(biāo)號(hào)，λ為L(zhǎng)的平衡特征，圖G稱(chēng)為平衡圖.

定義3［4］在含有n個(gè)頂點(diǎn)的兩個(gè)圈Cn（v）=v1v2…vnv1和Cn（u）=u1u2…unu1上，作圖2×Cn，使

見(jiàn)圖1.

圖1 圖2×CnFig.1Graph 2×Cn

定義4［5］對(duì)于簡(jiǎn)單圖G=（V，E），若存在雙值函數(shù)f∶E→｛ ｝-1，+1，使得?e∈E的鄰邊及e的集合N（e）滿

2 圖2×Cn的平衡性

定理1 當(dāng)n=4k時(shí)，圖2×Cn是平衡圖，且特征

證明 當(dāng)n=4k時(shí)，給出圖2×Cn的各頂點(diǎn)的標(biāo)號(hào)遞推算法L如下：

由文獻(xiàn)［4］可知，算法L給出的標(biāo)號(hào)是優(yōu)美標(biāo)號(hào).下證存在正整數(shù)使標(biāo)號(hào)L是圖2×Cn的

平衡標(biāo)號(hào).

3 圖2×Cn的符號(hào)邊控制數(shù)

定理2 圖2×Cn的符號(hào)邊控制數(shù)γ′s（2×Cn）=n，其中n=3，4，….

證明 首先證明γ′s（2×Cn）≤n.定義圖2×Cn的一個(gè)符號(hào)邊控制函數(shù)f如下：

容易驗(yàn)證：?e∈A∪B，有f（N［e］）=1；?e∈C，有f（N［e］）=3.由定義4知，f是圖2×Cn的一個(gè)符號(hào)邊控制函數(shù)，且，從而，所以

為證明方便，記Di=｛uivi，uiui+1，vivi+1｝，i=1，2，…，n.（特殊地Dn=｛unvn，unu1，vnv1｝），顯然則首先可以肯定：在圖2×Cn的任意符號(hào)邊控制函數(shù)f中Di（i=1，2，…，n）中至多包含2條-1邊.這是因?yàn)槿裟硞€(gè)Di中的三邊全為-1邊，即f（uivi）=f（uiui+1）=f（vivi+1）=-1，則

這與f是圖2×Cn的符號(hào)邊控制函數(shù)矛盾.故Di中至多包含2條-1邊.又設(shè)在圖2×Cn的任意符號(hào)邊控制函數(shù)f中+1邊和-1邊的條數(shù)分別為s和t，由定義有s-t，結(jié)合假設(shè)，得t＞n，即圖2×Cn中至少有n+1條-1邊.由鴿巢原理可知，至少存在一個(gè)Di中包含2條-1邊.不妨設(shè)Dk中包含2條-1邊，分兩種情況：

情況1：如圖2所示，若（fukvk）=（fukuk+1）=-1（（fukvk）=（fvkvk+1）=-1的情形討論是一樣的），則由符號(hào)邊控制函數(shù)f的定義，有

從而有f（uk-1vk-1）=f（uk-1uk）=f（vk-1vk）=1，即Dk的左鄰域Dk-1中的3條邊均為+1邊（見(jiàn)圖3）.

圖2 情況1 DkFig.2Case 1 Dk

圖3 情況1.1 Dk-1∪DkFig.3 Case1.1 Dk-1∪Dk

并且可進(jìn)一步討論得：Dk的右鄰域Dk+1中的3條邊中至多有1條-1邊.

這是因?yàn)?/p>

且N［uk+1vk+1］的閉邊鄰域的5條邊ukuk+1，vkvk+1，uk+1vk+1，uk+1uk+2，vk+1vk+2中，邊ukuk+1，vkvk+1中有且只有1條-1邊，則Dk+1中的3條邊uk+1vk+1，uk+1uk+2，vk+1vk+2，最多只能有1條-1邊.

情況2：如圖4所示，若f（ukuk+1）+f（vkvk+1）=-1，則由符號(hào)邊控制函數(shù)f的定義，有

從而有f（uk+1vk+1）=f（uk+1uk+2）=f（vk+1vk+2）=1，即Dk的右鄰域Dk+1中的3條邊均為+1邊（如圖5）.

圖4 情況2 DkFig.4Case 2 Dk

圖5 情況2.1 Dk∪Dk+1Fig.5 Case 2.1 Dk∪Dk+1

同樣可進(jìn)一步討論得：Dk的左鄰域Dk-1中的3條邊中至多有1條-1邊.

這是因?yàn)?/p>

且N［ukvk］的閉邊鄰域的5條邊ukuk+1，vkvk+1，ukvk，uk-1uk，vk-1vk中，邊ukuk+1，vkvk+1，ukvk中已有2條-1邊，則Dk-1中的邊uk-1uk，vk-1vk只能都取+1邊，從而Dk-1中的3條邊中至多有1條-1邊.

綜合上面兩種情況，結(jié)合假設(shè)，圖2×Cn中在去掉Dk-1∪Dk（情況1）或Dk∪Dk+1（情況2）后剩余的n-2個(gè)Di中至少有n-1條-1邊，同樣由鴿巢原理可知，至少存在某個(gè)Di中包含2條-1邊.設(shè)Dj中包含2條-1邊，同情況1或情況2，可得Dj的左鄰域或右鄰域中沒(méi)有-1邊.同理依次推下去可得，最后剩下一個(gè)單獨(dú)的Di至少包含2條-1邊或兩個(gè)相鄰的Di∪Di+1至少包含3條-1邊.

對(duì)于剩下一個(gè)單獨(dú)的Di至少包含2條-1邊的情況.由上面情況1和情況2的討論知：Di只能在圖2.1的右邊或圖5的左邊.而情況1中的討論知，圖2中Dk的右鄰域Dk+1中的3條邊中至多有1條-1邊，與Di至少包含2條-1邊矛盾.同樣由情況2中的討論知，圖4中Dk的左鄰域Dk-1中的3條邊中至多有1條-1邊，也與Di至少包含2條-1邊矛盾.

對(duì)于兩個(gè)相鄰的Di∪Di+1至少包含3條邊的情況.由于Di或Di+1中3條邊不能全為-1邊（當(dāng)然也不能全為+ 1邊），由情況1和情況2的討論，有Di∪Di+1的右邊不能是圖2，左邊不能是圖4.即Di∪Di+1的右邊只能是圖4，左邊只能是圖2.當(dāng)Di∪Di+1的右邊只能是圖4時(shí)，由情況2的討論知Di+1中至多有1條-1邊；當(dāng)Di∪Di+1的左邊只能是圖2時(shí)，由情況1的討論知Di中至多有1條-1邊，從而Di∪Di+1中至多有2條-1邊.這與Di∪Di+1至少包含3條-1邊矛盾.

結(jié)合證明中給出的符號(hào)邊控制函數(shù) f，γ′s（2×Cn）=n，定理2得證.

［1］徐保根.圖的控制與染色理論［M］.武漢：華中科技大學(xué)出版社，2013.

［2］Bandy J A，Murty U S R.Graph Theory with Application［M］.American Elsevier Publishing Co.，Inc.，New York，1976.

［3］馬克杰.優(yōu)美圖［M］.北京：北京大學(xué)出版社，1991.

［4］張玲瑛，林育青，鐘發(fā)勝，等.關(guān)于圖2×Cn的標(biāo)號(hào)［J］.北華大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，15（2）：174-178.

［5］Xu B.On signed edge domination Numbers of Graphs［J］.Discrete Math，2001，239：179-189.

［6］童細(xì)心.啞鈴圖2Cn+Pl的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性［J］.海南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，28（1）：15-19.

［7］童細(xì)心，林育青.圈Cn的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性［J］.西南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，39（8）：10-13.

［8］林育青，童細(xì)心，張玲瑛.太陽(yáng)圖的奇優(yōu)美性和奇強(qiáng)協(xié)調(diào)性［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2015，45（18）：271-280.

責(zé)任編輯：劉 紅

The Balance and Signed Edge Domination Number of Graph 2×Cn

TONG Xixin
（Department of Natural sciences，Shantou Polytechnic，Shantou 515041，China）

The article proves that graph 2×Cnis balanced when n=4k，withits featuresgiven andthe signed edge domination number determined.

graph 2×Cn；balanced graph；signed edge dominating function；signed edge domination number

O 157.5

A

1674-4942（2016）02-0123-04

2016-02-27

汕頭職業(yè)技術(shù)學(xué)院2015年院級(jí)科研課題（SZK2015Y23）