图2×Cn的平衡性和符号边控制数

童细心

（汕头职业技术学院 自然科学系，广东 汕头 515041）

图2×Cn的平衡性和符号边控制数

童细心

（汕头职业技术学院 自然科学系，广东 汕头 515041）

文章证明了图2×Cn在n=4k时是平衡图，给出了其平衡特征，并确定了图的符号边控制数.

图2×Cn；平衡图；符号边控制函数；符号边控制数

1 引言与预备知识

图的控制理论是图论中一个十分重要的内容，其研究内容也越来越广泛［1］.本文研究了一类图的平衡标号及其符号边控制数.设G=（V，E）为一个无向简单图，对任意e∈E，用NG（e）表示G中与e相邻的边集，NG［e］= NG（e）∪｛e｝为e的闭边邻域，在不引起混淆的情况下，简记为N（e）和N［e］.其他未加说明的定义和符号均来自文献［2］.

定义1［3］对于简单图G=（V，E），若∀v∈V，存在单射，且导出的边标号的双射，则称图G是优美图，称L为图G的优美标号.

定义2［3］设L为G的一个优美标号，若存在正整数λ，使得对任意，都有L（u）≤λ＜L（v）或L（v）≤成立，则称L为G的平衡标号，λ为L的平衡特征，图G称为平衡图.

定义3［4］在含有n个顶点的两个圈Cn（v）=v1v2…vnv1和Cn（u）=u1u2…unu1上，作图2×Cn，使

见图1.

图1 图2×CnFig.1Graph 2×Cn

定义4［5］对于简单图G=（V，E），若存在双值函数f∶E→｛ ｝-1，+1，使得∀e∈E的邻边及e的集合N（e）满

2 图2×Cn的平衡性

定理1 当n=4k时，图2×Cn是平衡图，且特征

证明 当n=4k时，给出图2×Cn的各顶点的标号递推算法L如下：

由文献［4］可知，算法L给出的标号是优美标号.下证存在正整数使标号L是图2×Cn的

平衡标号.

3 图2×Cn的符号边控制数

定理2 图2×Cn的符号边控制数γ′s（2×Cn）=n，其中n=3，4，….

证明 首先证明γ′s（2×Cn）≤n.定义图2×Cn的一个符号边控制函数f如下：

容易验证：∀e∈A∪B，有f（N［e］）=1；∀e∈C，有f（N［e］）=3.由定义4知，f是图2×Cn的一个符号边控制函数，且，从而，所以

为证明方便，记Di=｛uivi，uiui+1，vivi+1｝，i=1，2，…，n.（特殊地Dn=｛unvn，unu1，vnv1｝），显然则首先可以肯定：在图2×Cn的任意符号边控制函数f中Di（i=1，2，…，n）中至多包含2条-1边.这是因为若某个Di中的三边全为-1边，即f（uivi）=f（uiui+1）=f（vivi+1）=-1，则

这与f是图2×Cn的符号边控制函数矛盾.故Di中至多包含2条-1边.又设在图2×Cn的任意符号边控制函数f中+1边和-1边的条数分别为s和t，由定义有s-t，结合假设，得t＞n，即图2×Cn中至少有n+1条-1边.由鸽巢原理可知，至少存在一个Di中包含2条-1边.不妨设Dk中包含2条-1边，分两种情况：

情况1：如图2所示，若（fukvk）=（fukuk+1）=-1（（fukvk）=（fvkvk+1）=-1的情形讨论是一样的），则由符号边控制函数f的定义，有

从而有f（uk-1vk-1）=f（uk-1uk）=f（vk-1vk）=1，即Dk的左邻域Dk-1中的3条边均为+1边（见图3）.

图2 情况1 DkFig.2Case 1 Dk

图3 情况1.1 Dk-1∪DkFig.3 Case1.1 Dk-1∪Dk

并且可进一步讨论得：Dk的右邻域Dk+1中的3条边中至多有1条-1边.

这是因为

且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，则由符号边控制函数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

同样可进一步讨论得：Dk的左邻域Dk-1中的3条边中至多有1条-1边.

这是因为

且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边.

综合上面两种情况，结合假设，图2×Cn中在去掉Dk-1∪Dk（情况1）或Dk∪Dk+1（情况2）后剩余的n-2个Di中至少有n-1条-1边，同样由鸽巢原理可知，至少存在某个Di中包含2条-1边.设Dj中包含2条-1边，同情况1或情况2，可得Dj的左邻域或右邻域中没有-1边.同理依次推下去可得，最后剩下一个单独的Di至少包含2条-1边或两个相邻的Di∪Di+1至少包含3条-1边.

对于剩下一个单独的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边矛盾.

对于两个相邻的Di∪Di+1至少包含3条边的情况.由于Di或Di+1中3条边不能全为-1边（当然也不能全为+ 1边），由情况1和情况2的讨论，有Di∪Di+1的右边不能是图2，左边不能是图4.即Di∪Di+1的右边只能是图4，左边只能是图2.当Di∪Di+1的右边只能是图4时，由情况2的讨论知Di+1中至多有1条-1边；当Di∪Di+1的左边只能是图2时，由情况1的讨论知Di中至多有1条-1边，从而Di∪Di+1中至多有2条-1边.这与Di∪Di+1至少包含3条-1边矛盾.

结合证明中给出的符号边控制函数 f，γ′s（2×Cn）=n，定理2得证.

［1］徐保根.图的控制与染色理论［M］.武汉：华中科技大学出版社，2013.

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

［3］马克杰.优美图［M］.北京：北京大学出版社，1991.

［4］张玲瑛，林育青，钟发胜，等.关于图2×Cn的标号［J］.北华大学学报：自然科学版，2014，15（2）：174-178.

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

［6］童细心.哑铃图2Cn+Pl的奇优美性和奇强协调性［J］.海南师范大学学报：自然科学版，2015，28（1）：15-19.

［7］童细心，林育青.圈Cn的奇优美性和奇强协调性［J］.西南师范大学学报：自然科学版，2014，39（8）：10-13.

［8］林育青，童细心，张玲瑛.太阳图的奇优美性和奇强协调性［J］.数学的实践与认识，2015，45（18）：271-280.

责任编辑：刘 红

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

汕头职业技术学院2015年院级科研课题（SZK2015Y23）