兩類圖的符號(hào)控制數(shù)

任媛,趙凌琪,吉日木圖,王妍

(1.內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院,內(nèi)蒙古通遼市028043; 2.內(nèi)蒙古民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古通遼市028043; 3.山東水利職業(yè)學(xué)院信息工程系,山東日照276826)

兩類圖的符號(hào)控制數(shù)

任媛1,趙凌琪2,吉日木圖1,王妍3

(1.內(nèi)蒙古民族大學(xué)數(shù)學(xué)學(xué)院,內(nèi)蒙古通遼市028043; 2.內(nèi)蒙古民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，內(nèi)蒙古通遼市028043; 3.山東水利職業(yè)學(xué)院信息工程系,山東日照276826)

圖G的符號(hào)控制數(shù)(G)有著許多重要的應(yīng)用背景,因而確定其精確值有重要意義.Cm表示m個(gè)頂點(diǎn)的圈,n?Cm和n…Cm分別表示恰有一條公共邊或一個(gè)公共頂點(diǎn)的n個(gè)Cm的拷貝.給出了n?Cm和n…Cm的符號(hào)控制數(shù).

圖;符號(hào)控制函數(shù);符號(hào)控制數(shù)

1 引言

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

近些年來,圖的控制理論的研究越來越廣泛,各種控制概念相繼產(chǎn)生,例如符號(hào)邊控制,符號(hào)邊全控制,減控制,弱符號(hào)控制,符號(hào)星K控制等等,并獲得了一些初步的研究成果[2-6],尤其是對(duì)圖的符號(hào)控制,得到了許多新的結(jié)論[7-11].設(shè)圖G=(V,E).v∈V,v的開鄰域是與v相鄰接的頂點(diǎn)集合,即N(v)={u|uv∈E}.稱N(v)∪{v}為v的閉鄰域,記為N[v].

定義1.1[7]圖G=(V,E)的頂點(diǎn)集V上,定義一個(gè)雙值函數(shù)f:V→{?1,+1},并且f[v]=f(N[v]),若在任何一個(gè)頂點(diǎn)v的閉鄰域N[v]上函數(shù)值的和至少是1,即?v∈V, f(N[v])≥1,則稱函數(shù)f是G的一個(gè)符號(hào)控制函數(shù).一個(gè)符號(hào)控制函數(shù)的權(quán)重是

圖G的符號(hào)控制數(shù)γs(G)定義為γs(G)=min{f(V)|f是G的符號(hào)控制函數(shù)}.

定理1.1[7]對(duì)階為n≥3的圈圖

定理1.2[7]對(duì)完全圖Kn,有

定理1.3[7]星圖K1,m的符號(hào)控制數(shù)γs(K1,m)=m+1.

對(duì)二部圖Km,n(n≥m≥2),有下面兩個(gè)定理:

定理1.4[7]當(dāng)m=2,3時(shí),有

定理1.5[7]當(dāng)n≥m≥4時(shí),有

定理1.6[8]對(duì)任意正整數(shù)n≥2,扇圖

定理1.7[8]對(duì)任意正整數(shù)n≥3,輪圖

定理1.8[9]對(duì)于任意n階圖G,?和δ分別為圖G的最大度和最小度,則有

本文給出了n?Cm和n…Cm的符號(hào)控制數(shù).

2 主要結(jié)果

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

證明令表示n?Cm中的第i個(gè)m-圈,u和v表示的兩個(gè)公共頂點(diǎn),n?Cm中的第i個(gè)m-圈中余下的頂點(diǎn)依次為

設(shè)函數(shù)f是n?Cm的一個(gè)符號(hào)控制函數(shù),注意到:

下面分三種情況進(jìn)行討論.

情況1當(dāng)m≡0(mod 3)時(shí),考慮u和v的對(duì)稱性,只需討論下面三種情況.

情況1.1當(dāng)f(u)=f(v)=?1時(shí).

當(dāng)m=3時(shí),不滿足符號(hào)控制函數(shù)的定義,故下面考慮m>3時(shí),由

容易得到每個(gè)m-圈中余下(m?6)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)最多為現(xiàn)在考慮每個(gè)m-圈中余下(m?6)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)為時(shí),下面給出此時(shí)的一個(gè)符號(hào)控制函數(shù):

情況1.2當(dāng)f(u)=?1,f(v)=+1時(shí).

容易得到每個(gè)m-圈中余下(m?4)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)最多為現(xiàn)在考慮每個(gè)m-圈中余下(m?4)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)為時(shí),下面給出此時(shí)的一個(gè)符號(hào)控制函數(shù):

情況1.3當(dāng)f(u)=f(v)=+1時(shí).

下面討論n?Cm(m≡0(mod 3))中滿足上述條件的的個(gè)數(shù):

由

此時(shí),f是滿足要求的、權(quán)最小的一個(gè)符號(hào)控制函數(shù).

情況1.3.1當(dāng)n≡1(mod 2)時(shí),此時(shí)

情況1.3.2當(dāng)n≡0(mod 2)時(shí),此時(shí)

結(jié)合情況1.1,情況1.2,情況1.3,有

其中m≡0(mod 3).

情況2當(dāng)m≡1(mod 3)時(shí),考慮u和v的對(duì)稱性,只需討論下面三種情況.

情況2.1當(dāng)f(u)=f(v)=?1時(shí).

用情況1.1中同樣的方法,容易得到每個(gè)m-圈中余下(m?6)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)最多為現(xiàn)在考慮每個(gè)m-圈中余下(m?6)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)為時(shí),下面給出此時(shí)的一個(gè)符號(hào)控制函數(shù):

情況2.2當(dāng)f(u)=?1,f(v)=+1時(shí).

情況2.3當(dāng)f(u)=f(v)=+1時(shí).

結(jié)合情況2.1,情況2.2,情況2.3,有

情況3當(dāng)m≡2(mod 3)時(shí),考慮u和v的對(duì)稱性,只需討論下面三種情況.

情況3.1當(dāng)f(u)=f(v)=?1時(shí).

情況3.2當(dāng)f(u)=?1,f(v)=+1時(shí).

容易得到每個(gè)m-圈中余下(m?5)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)最多為現(xiàn)在考慮每個(gè)m-圈中余下(m?5)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)為時(shí),又由

此時(shí),f是滿足要求的、權(quán)最小的一個(gè)符號(hào)控制函數(shù).

情況3.2.1當(dāng)n≡1(mod 2)時(shí),此時(shí)

情況3.2.2當(dāng)n≡0(mod 2)時(shí),此時(shí)

情況3.3當(dāng)f(u)=f(v)=+1時(shí).

結(jié)合情況3.1,情況3.2,情況3.3,有

其中m≡2(mod 3).

綜上所述,對(duì)任意正整數(shù)m≥3,n≥2,

定理2.2對(duì)任意正整數(shù)m≥3,n≥2,

證明令表示n…Cm中的第i個(gè)m-圈,u表示的公共頂點(diǎn),n…Cm中的第i個(gè)m-圈中余下的頂點(diǎn)依次為

設(shè)函數(shù)f是n…Cm的一個(gè)符號(hào)控制函數(shù),注意到:

下面分三種情況進(jìn)行討論:

情況1當(dāng)m≡0(mod 3)時(shí).

下面給出此時(shí)的一個(gè)符號(hào)控制函數(shù):

情況2當(dāng)m≡1(mod 3)時(shí).

情況2.1當(dāng)f(u)=?1時(shí).

容易得到每個(gè)m-圈中余下(m?5)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)最多為現(xiàn)在考慮每個(gè)m-圈中余下(m?5)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)為時(shí),下面給出此時(shí)的一個(gè)符號(hào)控制函數(shù):

情況2.2當(dāng)f(u)=+1時(shí).

由容易得到每個(gè)m-圈中余下(m?1)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)最多為現(xiàn)在考慮每個(gè)m-圈中余下(m?1)個(gè)頂點(diǎn)中分配值為?1的個(gè)數(shù)為時(shí),下面給出此時(shí)的一個(gè)符號(hào)控制函數(shù):

結(jié)合情況2.1,情況2.2,有

情況3當(dāng)m≡2(mod 3)時(shí).

情況3.1當(dāng)f(u)=?1時(shí).

情況3.2當(dāng)f(u)=+1時(shí).

下面討論n…Cm(m≡2(mod 3))中滿足上述條件的的個(gè)數(shù):

由

此時(shí),f是滿足要求的、權(quán)最小的一個(gè)符號(hào)控制函數(shù).

情況3.2.1當(dāng)n≡1(mod 2)時(shí),此時(shí)

情況3.2.2當(dāng)n≡0(mod 2)時(shí),此時(shí)

結(jié)合情況3.1,情況3.2,有

綜上所述,對(duì)任意正整數(shù)m≥3,n≥2,

[1]Bondy J A,Murty U S R.Graph Theory With Applications[M].London:Macmillan,1977.

[2]Xu Baogen.On signed edge domination numbers of graphs[J].Discrete Math.,2001,239:179-189.

[3]Zhao Jinfeng,Xu Baogen.On signed edge total domination numbers of graphs[J].Journal of Mathematical Research Exposition,2011,31(2):209-214.

[4]Xu Baogen.On minus domination and signed domination in graphs[J].J.Math.Res.Exposition, 2003,23(4):586-590.

[5]尚華輝,苗連英,苗正科,等.關(guān)于圖的弱符號(hào)控制數(shù)的下界[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(4):691-695.

[6]李春華.圖的符號(hào)星K控制數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2009,25(4):638-641.

[7]于崇智,徐保根.圖的符號(hào)控制數(shù)[J].華東交通大學(xué)學(xué)報(bào),1997,14(4):54-58,67.

[8]于崇智.圖的最小符號(hào)控制函數(shù)的充要條件[J].陰山學(xué)刊,1999,15(1):5-8.

[9]徐保根,丁宗鵬,羅茜.圖的符號(hào)控制數(shù)的下界[J].華東交通大學(xué)學(xué)報(bào),2011,28(3):69-72.

[10]王軍秀.特殊圖類的符號(hào)控制數(shù)[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2005,21(1):59-61.

[11]徐保根.圖的控制理論[M].北京:科學(xué)出版社,2008.

Signed domination numbers for two class of graphs

Ren Yuan1,Zhao Lingqi2,Jirimutu1,Wang Yan3
(1.College of Mathematics,Inner Mongolia University for Nationalities,Tongliao028043,China; 2.College of Computer and Technology,Inner Mongolia University for Nationalities,Tongliao028043,China; 3.Department of Information Engineering,Shandong Water Polytechnic,Rizhao276826,China)

The signed domination number of a graph has its import and applying background,so it is useful to determinate the exact value of it.Cmdenotes the cycle of length m,n?Cmand n…Cmdenote the graph obtained from any n copies of Cmwhich have just one common edge and one common vertex,respectively.In this paper,we obtain the signed domination numbers of n?Cmand n…Cm.

graph,signed domination function,signed domination number

O157.5

A

1008-5513(2014)03-0271-09

10.3969/j.issn.1008-5513.2014.03.008

2012-06-07.

國(guó)家自然科學(xué)基金(61261025,61262018);內(nèi)蒙古民族大學(xué)校級(jí)研究項(xiàng)目(NMD1104).

任媛(1987-),碩士,助教,研究方向：圖論及其應(yīng)用.

2010 MSC:05C78