圖的最小嚴格強控制數*

龔奇娟，余桂東，丁 超

(安慶師范學院數學與計算科學學院，安徽 安慶 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