紅 霞, 馮 偉, 徐春雷, 吉日木圖

(1.內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院,內(nèi)蒙古通遼市028043； 2.內(nèi)蒙古民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,內(nèi)蒙古通遼市028043)

1 引 言

本文所指定的圖均為無向簡(jiǎn)單圖,文中未說明的符號(hào)和術(shù)語同文獻(xiàn)[1].

設(shè)G=(V,E)是一個(gè)圖,其頂點(diǎn)集V=V(G)和邊集E=E(G).對(duì)任意u∈V(G),則NG(u)為u點(diǎn)在G中的鄰域,NG[u]=NG(u)∪u為u點(diǎn)在G中的閉鄰域,δ=δ(G)和Δ=Δ(G)分別為圖G的最小度和最大度. 對(duì)一個(gè)圖G,若e=uv∈E(G),用NG(e)表示G中與e相鄰邊的集合,稱為e的邊鄰域,NG[e]=NG(e)∪{e}為e的閉鄰域,用dG(e)表示圖G的邊e的度.在不混淆的情況下,有時(shí)NG(e),NG[e],dG(e)分別簡(jiǎn)單記為N(e),N[e],d(e).如果d(v)是奇(偶)數(shù),則稱v是圖G的一個(gè)奇(偶)度點(diǎn).類似的,如果d(e)是奇(偶)數(shù),則稱e是圖G的一個(gè)奇(偶)度邊且d(e)=d(u)+d(v)-2.我們定義Eo=e∈E(G)d(e)是奇數(shù),Ee=e∈E(G)d(e)是偶數(shù).

2 基本概念

引理2設(shè)f為圖G的一個(gè)逆符號(hào)邊控制函數(shù)且e∈E(G).如果e∈Eo,則Σe′∈N[e]f(e′)≤0.如果e∈Ee,則Σe′∈N[e]f(e′)≤1.

引理3輪圖的逆符號(hào)邊控制數(shù)均為偶數(shù).

引理4扇圖的逆符號(hào)邊控制數(shù)均為奇數(shù).

近年來,圖的控制理論的研究越來越廣泛,各種控制概念相繼產(chǎn)生,圖的符號(hào)控制由Dunbar等人于1995年首先提出[2],國(guó)內(nèi)外許多圖論工作者對(duì)圖的符號(hào)控制進(jìn)行了研究,研究成果不斷豐富[3-8]. 徐保根于2001年定義了圖的符號(hào)邊控制[6].黃中升于2010年把圖的符號(hào)邊控制引申為圖的逆符號(hào)邊控制[8],并得到了一般圖的逆符號(hào)邊控制數(shù)的幾個(gè)上界.本文給出了所有輪圖和扇圖的逆符號(hào)邊控制數(shù).

設(shè)x為實(shí)數(shù)，用

x

e和

x

o分別表示不超過x的最大偶數(shù)和最大奇數(shù).用Wn+1=Cn+K1表示n+1階輪圖(即為K1鄰接Cn的每一個(gè)頂點(diǎn)而成的圖).用Fn+1=Pn+K1表示n+1階扇圖(即為K1鄰接Pn的每一個(gè)頂點(diǎn)而成的圖). 設(shè)G=(V,E)是一個(gè)圖,是一個(gè)實(shí)數(shù)集,對(duì)于實(shí)值函數(shù)f:E→和一個(gè)非空子集S?E(G),令f(S)=Σe∈Sf(e),并將f(E)稱為函數(shù)f的權(quán)重.下文中,為簡(jiǎn)單起見,我們稱適合f(e)=+1的邊為+1邊,稱適合f(e)=-1的邊為-1邊,并將f(N[e])記為f[e],記f(G)=f(E(G)).

3 主要結(jié)論

定理1對(duì)任意正整數(shù)n(n≥3)，有

γ'sWn+1 =n-13e.

Σe∈E(Cn)Σe′∈N[e]f(e′)≤n, 即 3f(Cn)+2f(K1.n)≤n.

γ'sWn+1 ≤n-13e.

情況1 當(dāng)n為奇數(shù)時(shí)，f(K1.n)總為奇數(shù).顯然f(K1.n)≤3(否則任取e∈E(K1.n)有Σe′∈N[e]fe′≥3,矛盾).

情況1.3 當(dāng)f(K1.n)≤-1時(shí),若n=6k+1,則

γ'sWn+1 ≤n-13=n-13e .

γ'sWn+1 ≤n-13=n-13e+23.

γ'sWn+1 ≤n-13e.

γ'sWn+1 ≤n-13=n-13e+43.

γ'sWn+1 ≤n-13e.

情況2 當(dāng)n為偶數(shù)時(shí)，f(K1.n)總為偶數(shù)且f(K1.n)≤2.

情況2.3 當(dāng)f(K1.n)≤-2時(shí),若n=6k+2,則

γ'sWn+1 ≤n-23=n-13e

γ'sWn+1 ≤n-23=n-13e+23 .

γ'sWn+1 ≤n-13e.

γ'sWn+1 ≤n-23=n-13e+43.

γ'sWn+1 ≤n-13e.

γ'sWn+1 ≤n-13e.

接下來我們證明

γ'sWn+1 ≥n-13e.

下面僅需定義Wn+1的一個(gè)逆符號(hào)邊控制函數(shù)f使得fWn+1=

e.

令Wn+1的中心點(diǎn)為v0,即V(K1)=v0,Cn上的頂點(diǎn)依次記為v1,v2,…,vn.顯然有

E(Wn+1)=v0vi1≤i≤n∪vjvj+11≤j≤n-1∪vnv1,E(Wn+1)=2n.

(1)當(dāng)n為奇數(shù)時(shí)，定義一個(gè)函數(shù)f：

其下標(biāo)對(duì)n取模

(2) 當(dāng)n為偶數(shù)時(shí)，定義一個(gè)函數(shù)f：

γ'sWn+1 ≥fWn+1 =n-13e,

其下標(biāo)對(duì)n取模.容易驗(yàn)證 故有

γ'sWn+1 =n-13e.

定理2對(duì)任意正整數(shù)n(n≥3)，有

γ'sFn+1 =n3o.

證令扇圖Fn+1的扇心為v0,即V(K1)=v0,Pn上的頂點(diǎn)依次記為v1,v2,…,vn.顯然有

EFn+1=v0vi1≤i≤n∪{vjvj+11≤j≤n-1}，E(Fn+1=2n-1.

3fPn+2fK1.n-fv1v2-fvn-1vn-fv0v1-fv0vn≤n-1.

下面首先證明

γ'sFn+1 ≤n3o.

情況1 當(dāng)n為奇數(shù)時(shí)f(K1.n)總為奇數(shù)且f(K1.n)≤1.

情況1.1 當(dāng)f(K1.n)=1時(shí),f(Pn)≤0,故

fPn ≤22n-1 3-n+1.

情況1.2 當(dāng)f(K1.n)=-1時(shí)，若n≡1(mod 3)，則故

γ'sFn+1 =fFn+1 =fPn +fK1.n ≤22(n-1)3n≤n3o.

fPn ≤22(n-1)3-n+1,

當(dāng)n≡2(mod 3)時(shí),故

γ'sFn+1 =fFn+1 =fPn +fK1.n ≤22(n-1)3n≤n3o.

fPn ≤22(n-1)3-n+1,

當(dāng)n≡0(mod 3)時(shí),故

γ'sFn+1 =fFn+1 =fPn +fK1.n ≤22(n-1)3n≤n3o.

情況1.3 當(dāng)f(K1.n)≤-3時(shí),若n=6k+1,則

γ'sFn+1 ≤n+3+fK1.n 3=n3o+43.

γ'sFn+1 ≤n3o.

由引理4知，若n=6k+3,則

γ'sFn+1 ≤n+3+fK1.n 3=n3o.

若n=6k+5,則

γ'sFn+1 ≤n+3+fK1.n 3=n3o+23.

由引理4知，

γ'sFn+1 ≤n3o.

情況2 當(dāng)n為偶數(shù)時(shí)，f(K1.n)總為偶數(shù)且f(K1.n)≤2.

情況2.1 當(dāng)f(K1.n)=2時(shí),f(Pn)=-(n-1),故

fPn ≤24n-16-n+1.

情況2.3 當(dāng)f(K1.n)=-2時(shí)，若n≡0,1(mod 3),則故

γ'sFn+1 =fFn+1 =fPn +fK1.n ≤24n-16-n-1≤n3o.

fPn ≤24n-16-n+1.

當(dāng)n≡2(mod 3)時(shí),故

γ'sFn+1 =fFn+1 =fPn +fK1.n ≤24n-16-n-1≤n3o.

γ'sFn+1 ≤n+3+fK1.n 3=n3o+43.

γ'sFn+1 ≤n3o.

γ'sFn+1 ≤n+3+fK1.n 3=n3o.

γ'sFn+1 ≤n+3+fK1.n 3=n3o+23.

γ'sFn+1 ≤n3o.

情況2.4 當(dāng)f(K1.n)≤-4時(shí),若n=6k+2，則由引理4知若n=6k+4,則若n=6k+6,則由引理4知綜合以上兩種情況有

γ'sFn+1 ≤n3o.

γ'sFn+1 ≥n3o.

接下來證明下面僅需定義f使得

fFn+1 ≤n3o.

(1)當(dāng)n為偶數(shù)時(shí)，若n≡0,1(mod 3)，定義一個(gè)函數(shù)f：

若n≡2(mod 3)，定義一個(gè)函數(shù)f：

(2)當(dāng)n為奇數(shù)時(shí)，若n≡1,2(mod 3)，定義一個(gè)函數(shù)f：

若n≡0(mod 3)且n≡9(mod 12)，定義一個(gè)函數(shù)f：

f(e)=-1,當(dāng)e=v0vn2',(-1)i+1,當(dāng)e=v0vi或e=v0vn-i+1,1≤i≤n-12,+1,當(dāng)e=vjvj+1或e=vn-jvn-j+1,j≡0,1(mod 3),1≤j≤n-12,-1,當(dāng)e=vjvj+1或e=vn-jvn-j+1,j≡2(mod 3),1≤j≤n-12..

若n≡0(mod 3)且n≡3(mod 12)，定義一個(gè)函數(shù)f：

f(e)=+1,當(dāng)e=v0vn2,(-1)i+1,當(dāng)e=v0vi或e=v0vn-i+1,1≤i≤4,(-1)i,當(dāng)e=v0vi或e=v0vn-i+1,5≤i≤n2,+1,當(dāng)e=vjvj+1或e=vn-jvn-j+1,j=1,3,4,-1,當(dāng)e=vjvj+1或e=vn-jvn-j+1,j=2,+1,當(dāng)e=vjvj+1,j=4+k,k≡0,1(mod 3),-1,當(dāng)e=vjvj+1,j=4+k,k≡2(mod 3). k=1,2,…,n-9

γ'sFn+1 ≤fFn+1 =n3o.

容易驗(yàn)證故有

γ'sFn+1 =n3o.

[參 考 文 獻(xiàn)]

[1] Bondy J A and Murty U S R.Graph theory with applications [M]. London and Elsevier: Macmillan, 1976.

[2] Dnbar J. Hedetniemi S,.Henning A, Slater J. Signed domination in graphs[C]. New York: Wiley. Graph Theory, Combinatorics and Applications. 1995.

[3] Hattingh J H, Ungerer E, Henning M A. Partial signed domination in graphs[J]. Ars Combinatoria, 1998,48:33-42.

[4] Zhang Z, Xu B, Li Y, Liu L. A note on the lower bounds of signed domination number of a graph[J]. Discrete Mathematics, 1999,195(1):295-298.

[5] Zelinka B. Signed total domination number of a graph[J]. Czechoslovak Mathematicical Journal, 2001,51(2): 225-229.

[6] Xu Baogen . On signed edge domination numbers of graphs[J]. Discrete Math., 2001,239(1-3):179-189.

[7] Xu Baogen. On signed edge domination numbers of graphs[J].Discrete Math, 2005,294(3):311-316.

[8] Huang Zhongsheng , Xing Huaming Xing, Zhao Yanbing. The upper bounds of inverse signed edge domination numbers of graph[J]. ActaMathematicaeApplicataeSinica, 2010,33(5):840-846.