丁　超

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

?

關(guān)于圖的嚴(yán)格強(qiáng)控制數(shù)的界

丁超

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

摘要：圖的控制數(shù)有著重要的應(yīng)用背景，嚴(yán)格強(qiáng)控制數(shù)是圖的眾多控制數(shù)中的一種。本文得到n階圖的嚴(yán)格強(qiáng)控制數(shù)的下界，并給出一些特殊圖類的嚴(yán)格強(qiáng)控制數(shù)的上界。

關(guān)鍵詞：嚴(yán)格強(qiáng)控制數(shù)； 歐拉圖； 方格圖； 奇偶性

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.001

隨著科技的發(fā)展，圖論也有著長(zhǎng)足的進(jìn)步，而控制數(shù)是該研究領(lǐng)域中發(fā)展最快的分支之一，嚴(yán)格強(qiáng)控制數(shù)是其中的一種。 早在1862年Jaenisch就提出控制數(shù)，直到1962年才由Ore形成控制理論。 1998年Michael A. Henning等提出嚴(yán)格強(qiáng)控制數(shù)[1]。 實(shí)際上，判斷任意給定的n階圖的各種控制數(shù)是NPC問(wèn)題，所以給出它們的界就顯得非常重要。 關(guān)于圖的其他各種控制數(shù)已有很多精彩的結(jié)論[2-6]，但嚴(yán)格強(qiáng)控制數(shù)方面的研究結(jié)果卻很少[7-8]。 其中文獻(xiàn)[1]得到了樹(shù)的嚴(yán)格強(qiáng)控制數(shù)的界，其界與圖的階的奇偶有關(guān)，與階的大小無(wú)關(guān)。 實(shí)際上當(dāng)圖是一些特殊樹(shù)的時(shí)候，此界還可以縮小。本文討論n階圖的嚴(yán)格強(qiáng)控制數(shù)的下界，給出歐拉圖、路、方格圖的嚴(yán)格強(qiáng)控制數(shù)的上界，此界比文獻(xiàn)[1]中給出的界要小，且與圖的階的奇偶無(wú)關(guān)，而與階的大小有關(guān)。

文中只考慮簡(jiǎn)單無(wú)向圖，以下給出本文相關(guān)的圖論術(shù)語(yǔ)、記號(hào)(未說(shuō)明的見(jiàn)文獻(xiàn)[9])及相關(guān)引理。

設(shè)圖G=(V,E)，函數(shù) f∶V→{-1,1}，使得V中的多于一半的點(diǎn)v有f[v]≥1，則稱f為G的嚴(yán)格強(qiáng)控制函數(shù), 記

s(G)=min{f(V)|f為G上的嚴(yán)格強(qiáng)控制函數(shù)}，

稱s(G)為圖G的嚴(yán)格強(qiáng)控制數(shù)[7]。

引理1[9]若G=(V,E)為n階歐拉圖，則對(duì)任意v∈V，有d(v)為偶數(shù)。

引理2若G=(V,E)為n階歐拉圖，f為V上的嚴(yán)格強(qiáng)控制函數(shù), 則對(duì)任意v∈V，有f[v]≠0。

下面給出本文的主要內(nèi)容。

定理1設(shè)G=(V,E)為n階圖，n≥5，則s(G)≥4-n。

證明構(gòu)造G如圖1所示，V=V1∪V2，V1={v1,v2}，V2={v3,v4,…,vn-1,vn}，其中vi與V1中的兩點(diǎn)都相鄰(i=3,…,n)，V2中的任意兩點(diǎn)不相鄰，V1中的兩點(diǎn)相鄰或者不相鄰。定義

由n≥5知f[v1]=f[v2]≤0，f[vi]=f(v1)+f(v2)+f(vi)=1+1-1=1≥1，i=3,…,n。而n-2>2，即有多于一半的點(diǎn)v有f[v]≥1，所以f是V上的嚴(yán)格強(qiáng)控制函數(shù)，且

f(V)=f(v1)+f(v2)+f(v3)+f(v4)+…+f(vn-1)+f(vn)=2-(n-2)=4-n。

對(duì)任意n階圖G=(V,E)，n≥5，如果f是V上的嚴(yán)格強(qiáng)控制函數(shù)，那么至少有兩個(gè)點(diǎn)賦1，所以s(G)≥4-n，圖1是等號(hào)成立的極圖。

圖1

計(jì)算f[v]，由引理2知f[v]≠0，則有兩種情形：

②沒(méi)有一半以上的v有f[v]>0，令f′(v)=

綜上所述，當(dāng)G為奇數(shù)階歐拉圖時(shí)，s(G)≤1。

計(jì)算g[v]，由引理2知g[v]≠0，則有兩種情形：

②沒(méi)有一半以上的v有g(shù)[v]>0，令g′(v)=

綜上所述，當(dāng)G為偶數(shù)階歐拉圖時(shí)，s(G)≤2， 所以結(jié)論成立。

由于圈是特殊的歐拉圖，所以有下面的結(jié)論。

推論1若圖為n階圈Cn，則

綜合文獻(xiàn)[1]中的定理8和定理14可得樹(shù)的嚴(yán)格強(qiáng)控制數(shù)的上界，即

定理3[1]若圖為n(n≥4)階樹(shù)T，則

由定理3知樹(shù)的嚴(yán)格強(qiáng)控制數(shù)的上界只與它階的奇偶有關(guān)，與階的大小無(wú)關(guān)。 但是當(dāng)樹(shù)是一些特殊樹(shù)的時(shí)候，此界還可以縮小，比如當(dāng)樹(shù)是一條路P15時(shí)，s(P15)≤-3。 關(guān)于路的嚴(yán)格強(qiáng)控制數(shù)的結(jié)論如下。

定理4若圖為n(n≥3)階路Pn，則

證明設(shè)Pn為n階路，令

定義函數(shù)

圖2

證明設(shè)圖Ln×m為n×m(n≥3,m≥2)階方格圖，記第i行第j列的點(diǎn)為vij，定義函數(shù)

由f的定義知

-1+1+1=1>0。

1+1-1=1>0；

1+1=2>0。

參考文獻(xiàn):

[1] Michael A H,Hugh R H.Strict majority functions on graphs[J]. Journal of Graph Theory, 1998, 28: 49-56.

[2] Dunber J.Signed Domination in Graph, Graph Theory, Combinatorics and Applications[M]. New York: Wiley, 1995: 311-322.

[3] Zhang Z,Zu B,Li Y, et al.A note on the lower bounds of signed domination number of a graph[J]. Discrete Math,1999, 195: 295-298.

[4] Zu B. On signed edge domination numbers of graphs[J]. Discrete Math,2001,239：179-189.

[5] Cockayne E J,Mynhardt C.On a generalization of signed dominating function of graphs[J].Ars Combinatoria,1996, 43: 234-245.

[6] Hattingh J H,Ungerer E.The signed and minus -subdomination numbers of comets[J]. Discrete Math,1998,183:141-152.

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

[8] 龔奇娟, 余桂東,丁超. 圖的最小嚴(yán)格強(qiáng)控制數(shù)[J]. 菏澤學(xué)院學(xué)報(bào), 2013, 35(2): 1-4.

[9] Bondy J A,Marty O S R.Graph Theory with Application[M]. New York: Macmillan, Landon and Elsevier, 1976.

Bounds of the Strict Majority Domination Number of Graphs

DING Chao

(School of Mathematics and Computational Science, Anqing Normal University, Anqing, Anhui 246133, China)

Abstract:The domination numbers of graphs have many applications. The strict majority domination number is one of many domination numbers of graphs. In this paper, a lower bound of the domination numbers of graphs is obtained and some upper bounds of strict majority domination number of special graphs are given.

Key words:strict majority domination number; Euler graph; lattice; parity

* 收稿日期：2015-09-30

基金項(xiàng)目：安徽省高等學(xué)校自然科學(xué)基金(KJ2015ZD27，AQKJ2015B010)。

作者簡(jiǎn)介：丁超，男，安徽無(wú)為人，碩士，安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院講師，研究方向?yàn)閳D論與組合優(yōu)化。 E-mail: 75360143@qq.com

中圖分類號(hào)：O157.5

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1007-4260(2016)02-0001-03

網(wǎng)絡(luò)出版時(shí)間：2016-06-08 12:57網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.001.html