龚奇娟，余桂东，丁 超

(安庆师范学院数学与计算科学学院，安徽 安庆 246133)

图的最小严格强控制数*

龚奇娟，余桂东，丁 超

(安庆师范学院数学与计算科学学院，安徽 安庆 246133)

设K1,n为星图，K1,n+me为K1,n任意加m条边所得到的图．首先研究了K1,n的严格强控制数，K1,n+e的严格强控制数；其次研究了形如K1,n+me的图类中图的最小严格强控制数以及此类图中达到最小严格强控制数的极小图；最后给出具有n个顶点的图类中图的最小严格强控制数．

星图；简单图；严格强控制函数；严格强控制数

引言

设图G={V,E}，对于v∈V,N[v]={u|uv∈E}∪{v}称为v的闭邻域，函数f：V→{-1,1} ，记f的权为f(V)=∑v∈Vf(v),且记f[v]=∑u∈N[v]f(u).

定义1 函数f：V→{-1,1} ，使得V中所有顶点v都有f[v]≥1，则称f为G的V上的符号控制函数，min{f(V)|f为G上的符号控制函数}称为图的符号控制数．

定义2 函数f：V→{-1,1} ，使得V中的多于一半的点v有f[v]≥1，则称f为G的V上的严格强控制函数，smaj(G)=min{f(V)|f为G上的严格强控制函数}称为图的严格强控制数．

图的严格强控制数是图的符号控制数的推广．对于图的符号控制数，已经有了较多的结果，但严格强控制数的结果很少，如文献[1～3]．

记Kn为n阶完全图，Kn-e为Kn上去掉一条边所得到的图，K1,n为星图，K1,n+me为星图K1,n任意加m条边所得到的图．文献[1]研究了l个Kn的并的严格强控制数，Kn与任意m阶图的联图的严格强控制数．文献[2]研究了Kn与任意m阶图的并的严格强控制数，Kn与其补图的严格强控制数，Kn与Km补图的严格强控制数．文献[3]研究了Kn与Kn-e严格强控制数，Kn-e与任意m阶图的并的严格强控制数．本文主要讨论了K1,n的严格强控制数，K1,n+e的严格强控制数，并进一步研究了形如K1,n+me的图类中图的最小严格强控制数，且此类图中达到最小严格强控制数的极小图，以及具有n个顶点的图类中图的最小严格强控制数．本文所考虑的图均为简单无向图，未说明的术语与符号见文献[4]．

1 主要结论

图1 星图

证明设f为K1,n的V上的严格强控制函数.若有

f(v0)=-1，则f在vi(i=1,2,…,n)上无论是赋值1还是-1，

都有f[vi]lt;1(i=1,2,…,n)，这与f为K1,n的V上的严格强控制函数矛盾，所以必有f(v0)=1.

定理2设K1,n+e为星图K1,n(n≥2)任意加一条边所得到的简单图，则：

证明设f为K1,n+e的V上的严格强控制函数．下面不妨设e=v1v2．若有f(v0)=-1，由严格强控制函数的定义，必有f(v1)=f(v2)=1．若令：

则f'也为K1,n+e的V上的严格强控制函数，且f'(V(K1,n+e))=f(V(K1,n+e))，故下面可令f(v0)=1．

若有f(v1)=f(v2)=1，令：

则f'也为K1,n+e的V上的严格强控制函数，且有f'(V(K1,n+e))lt;f(V(K1,n+e))．

若有f(v1)=f(v2)=-1，由严格强控制函数的定义，必存在点vs(s∈{3,…,n})使得f(vs)=1．令：

则f'也为K1,n+e的V上的严格强控制函数，且有f'(V(K1,n+e))=f(V(K1,n+e))，故下面可令f(v1)=1,f(v2)=-1．

证明完毕．

min{smaj(G),G∈M}=3-n

证明设f为K1,n+me的V上的严格强控制函数，且v0为K1,n的中心，若有f(v0)=-1，由严格强控制函数的定义，必存在点vt(t∈{1,2,…,n})使得f(vt)=1．若令：

则f'也为K1,n+me的V上的严格强控制函数，且f'(V(K1,n+me))=f(V(K1,n+me))，故下面可令f(v0)=1．

再由严格强控制函数的定义，仍存在点vt(t∈{1,2,…,n})使得f(vt)=1．这样，min{smaj(G),G∈M}≥3-n.

若f在K1,n+me中除v0,vt两点外，都赋值为-1．

所以，min{smaj(G),G∈M}=3-n．

要使f(V(K1,n+me))=3-n，此时f在V(K1,n+me)上赋值恰有2个为1，其它均为-1，故可令

1)当n为偶数时的情形

2)当n为奇数时的情形

定理4设H为具有n≥2个顶点的简单图类，则min{smaj(G),G∈H}=4-n.

证明设f为图G的V上的严格强控制函数，则f在V(G)上至少有两个点的赋值为1，这样min{smaj(G),G∈H}≥4-n．当n=2，显然有smaj(G)=2；当n≥3，由定理3知min{samj(G),G∈H}=4-n．所以，min{smaj(G),G∈H=4-n．证明完毕．

[1]任庆军. 一些特定图类的严格强控制数[J]. 淮阴师范学院学报：自然科学版,2002,1(3)：10-12.

[2]任庆军，傅英定．关于图的并的严格强控制数[J]. 电子科技大学学报,2004,33(4):478-480.

[3]倪贝贝，叶淼林．图的并的严格强控制数的若干新结论[J]. 安庆师范学院学报，2012,18(2)：35-36.

[4]Bondy J A，Murty U S R． Graph Theory with Application [M]. New York ：Macmillan, London and Elsevier, 1976.

MinimumStrictMajorDominationNumberofGraphs

GONG Qi-juan, YU Gui-dong, DING Chao

(School of Mathematics and Computation Sciences, Anqing Normal University, Anqing,Anhui 246133,China )

Let be a star. be a graph, obtained by arbitrarily adding edges to. Firstly, we determine the strict majority domination numbers of and. Secondly, we give the minimum strict majority domination number of the class of and the minimum graphs on strict major domination number of the class of. Finally, we give the minimum strict majority domination number of the class of graph with vertices.

star；simple graph；strict majority domination function numbers；strict majority domination numbers

1673-2103(2013)02-0001-04

2013-03-04

安徽高校省级科学研究重点项目(KJ2011A195)

龚奇娟(1987-)，女，湖北枣阳人，在读硕士研究生，研究方向：图论及其应用．

余桂东(1973-)，女，安徽潜山人，副教授，博士，研究方向：图论及其应用．

O157.5

A