龔奇娟，余桂東，丁 超

(安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

圖的最小嚴(yán)格強(qiáng)控制數(shù)*

龔奇娟，余桂東，丁 超

(安慶師范學(xué)院數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

設(shè)K1,n為星圖，K1,n+me為K1,n任意加m條邊所得到的圖．首先研究了K1,n的嚴(yán)格強(qiáng)控制數(shù)，K1,n+e的嚴(yán)格強(qiáng)控制數(shù)；其次研究了形如K1,n+me的圖類中圖的最小嚴(yán)格強(qiáng)控制數(shù)以及此類圖中達(dá)到最小嚴(yán)格強(qiáng)控制數(shù)的極小圖；最后給出具有n個頂點(diǎn)的圖類中圖的最小嚴(yán)格強(qiáng)控制數(shù)．

星圖；簡單圖；嚴(yán)格強(qiáng)控制函數(shù)；嚴(yán)格強(qiáng)控制數(shù)

引言

設(shè)圖G={V,E}，對于v∈V,N[v]={u|uv∈E}∪{v}稱為v的閉鄰域，函數(shù)f：V→{-1,1} ，記f的權(quán)為f(V)=∑v∈Vf(v),且記f[v]=∑u∈N[v]f(u).

定義1 函數(shù)f：V→{-1,1} ，使得V中所有頂點(diǎn)v都有f[v]≥1，則稱f為G的V上的符號控制函數(shù)，min{f(V)|f為G上的符號控制函數(shù)}稱為圖的符號控制數(shù)．

定義2 函數(shù)f：V→{-1,1} ，使得V中的多于一半的點(diǎn)v有f[v]≥1，則稱f為G的V上的嚴(yán)格強(qiáng)控制函數(shù)，smaj(G)=min{f(V)|f為G上的嚴(yán)格強(qiáng)控制函數(shù)}稱為圖的嚴(yán)格強(qiáng)控制數(shù)．

圖的嚴(yán)格強(qiáng)控制數(shù)是圖的符號控制數(shù)的推廣．對于圖的符號控制數(shù)，已經(jīng)有了較多的結(jié)果，但嚴(yán)格強(qiáng)控制數(shù)的結(jié)果很少，如文獻(xiàn)[1～3]．

記Kn為n階完全圖，Kn-e為Kn上去掉一條邊所得到的圖，K1,n為星圖，K1,n+me為星圖K1,n任意加m條邊所得到的圖．文獻(xiàn)[1]研究了l個Kn的并的嚴(yán)格強(qiáng)控制數(shù)，Kn與任意m階圖的聯(lián)圖的嚴(yán)格強(qiáng)控制數(shù)．文獻(xiàn)[2]研究了Kn與任意m階圖的并的嚴(yán)格強(qiáng)控制數(shù)，Kn與其補(bǔ)圖的嚴(yán)格強(qiáng)控制數(shù)，Kn與Km補(bǔ)圖的嚴(yán)格強(qiáng)控制數(shù)．文獻(xiàn)[3]研究了Kn與Kn-e嚴(yán)格強(qiáng)控制數(shù)，Kn-e與任意m階圖的并的嚴(yán)格強(qiáng)控制數(shù)．本文主要討論了K1,n的嚴(yán)格強(qiáng)控制數(shù)，K1,n+e的嚴(yán)格強(qiáng)控制數(shù)，并進(jìn)一步研究了形如K1,n+me的圖類中圖的最小嚴(yán)格強(qiáng)控制數(shù)，且此類圖中達(dá)到最小嚴(yán)格強(qiáng)控制數(shù)的極小圖，以及具有n個頂點(diǎn)的圖類中圖的最小嚴(yán)格強(qiáng)控制數(shù)．本文所考慮的圖均為簡單無向圖，未說明的術(shù)語與符號見文獻(xiàn)[4]．

1 主要結(jié)論

圖1 星圖

證明設(shè)f為K1,n的V上的嚴(yán)格強(qiáng)控制函數(shù).若有

f(v0)=-1，則f在vi(i=1,2,…,n)上無論是賦值1還是-1，

都有f[vi]lt;1(i=1,2,…,n)，這與f為K1,n的V上的嚴(yán)格強(qiáng)控制函數(shù)矛盾，所以必有f(v0)=1.

定理2設(shè)K1,n+e為星圖K1,n(n≥2)任意加一條邊所得到的簡單圖，則：

證明設(shè)f為K1,n+e的V上的嚴(yán)格強(qiáng)控制函數(shù)．下面不妨設(shè)e=v1v2．若有f(v0)=-1，由嚴(yán)格強(qiáng)控制函數(shù)的定義，必有f(v1)=f(v2)=1．若令：

則f'也為K1,n+e的V上的嚴(yán)格強(qiáng)控制函數(shù)，且f'(V(K1,n+e))=f(V(K1,n+e))，故下面可令f(v0)=1．

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

則f'也為K1,n+e的V上的嚴(yán)格強(qiáng)控制函數(shù)，且有f'(V(K1,n+e))lt;f(V(K1,n+e))．

若有f(v1)=f(v2)=-1，由嚴(yán)格強(qiáng)控制函數(shù)的定義，必存在點(diǎn)vs(s∈{3,…,n})使得f(vs)=1．令：

則f'也為K1,n+e的V上的嚴(yán)格強(qiáng)控制函數(shù)，且有f'(V(K1,n+e))=f(V(K1,n+e))，故下面可令f(v1)=1,f(v2)=-1．

證明完畢．

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

證明設(shè)f為K1,n+me的V上的嚴(yán)格強(qiáng)控制函數(shù)，且v0為K1,n的中心，若有f(v0)=-1，由嚴(yán)格強(qiáng)控制函數(shù)的定義，必存在點(diǎn)vt(t∈{1,2,…,n})使得f(vt)=1．若令：

則f'也為K1,n+me的V上的嚴(yán)格強(qiáng)控制函數(shù)，且f'(V(K1,n+me))=f(V(K1,n+me))，故下面可令f(v0)=1．

再由嚴(yán)格強(qiáng)控制函數(shù)的定義，仍存在點(diǎn)vt(t∈{1,2,…,n})使得f(vt)=1．這樣，min{smaj(G),G∈M}≥3-n.

若f在K1,n+me中除v0,vt兩點(diǎn)外，都賦值為-1．

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

要使f(V(K1,n+me))=3-n，此時(shí)f在V(K1,n+me)上賦值恰有2個為1，其它均為-1，故可令

1)當(dāng)n為偶數(shù)時(shí)的情形

2)當(dāng)n為奇數(shù)時(shí)的情形

定理4設(shè)H為具有n≥2個頂點(diǎn)的簡單圖類，則min{smaj(G),G∈H}=4-n.

證明設(shè)f為圖G的V上的嚴(yán)格強(qiáng)控制函數(shù)，則f在V(G)上至少有兩個點(diǎn)的賦值為1，這樣min{smaj(G),G∈H}≥4-n．當(dāng)n=2，顯然有smaj(G)=2；當(dāng)n≥3，由定理3知min{samj(G),G∈H}=4-n．所以，min{smaj(G),G∈H=4-n．證明完畢．

[1]任慶軍. 一些特定圖類的嚴(yán)格強(qiáng)控制數(shù)[J]. 淮陰師范學(xué)院學(xué)報(bào)：自然科學(xué)版,2002,1(3)：10-12.

[2]任慶軍，傅英定．關(guān)于圖的并的嚴(yán)格強(qiáng)控制數(shù)[J]. 電子科技大學(xué)學(xué)報(bào),2004,33(4):478-480.

[3]倪貝貝，葉淼林．圖的并的嚴(yán)格強(qiáng)控制數(shù)的若干新結(jié)論[J]. 安慶師范學(xué)院學(xué)報(bào)，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

安徽高校省級科學(xué)研究重點(diǎn)項(xiàng)目(KJ2011A195)

龔奇娟(1987-)，女，湖北棗陽人，在讀碩士研究生，研究方向：圖論及其應(yīng)用．

余桂東(1973-)，女，安徽潛山人，副教授，博士，研究方向：圖論及其應(yīng)用．

O157.5

A