尹 凱，陳學(xué)剛

（華北電力大學(xué)數(shù)理學(xué)院，北京 102200）

完全多部圖的符號(hào)羅馬控制數(shù)

尹 凱，陳學(xué)剛

（華北電力大學(xué)數(shù)理學(xué)院，北京 102200）

設(shè)圖G＝（V，E）是一個(gè)簡(jiǎn)單無(wú)向圖，若實(shí)值函數(shù)f:V→{-1，1，2}滿足以下兩個(gè)條件：（i）對(duì)于任意v∈V，均有∑u∈N[v]f（u）≥1成立；（ii）任意v∈V，若f（v）＝-1，則存在一個(gè)與v相鄰的頂點(diǎn)u∈V，滿足f（u）＝2，則稱該函數(shù)為圖G的符號(hào)羅馬控制函數(shù).定義圖的符號(hào)羅馬控制數(shù)為是圖G的符號(hào)羅馬控制函數(shù)}.通過對(duì)完全多部圖中的頂點(diǎn)數(shù)進(jìn)行分類，給出了當(dāng)k≥3時(shí)，完全多部圖K（n1，…，ni，…，nk）的符號(hào)羅馬控制數(shù)的準(zhǔn)確值.

完全多部圖；符號(hào)羅馬控制函數(shù)；符號(hào)羅馬控制數(shù)

0 引言

文中所指的圖均為簡(jiǎn)單無(wú)向圖，文中符號(hào)和術(shù)語(yǔ)同文獻(xiàn)[1].

設(shè)圖G＝（V，E）是一個(gè)簡(jiǎn)單無(wú)向圖，V（G）和E（G）分別是圖G的頂點(diǎn)集和邊集.令頂點(diǎn)v的開鄰域N（v）是指圖G中所有與v相鄰的點(diǎn)的集合.頂點(diǎn)v的閉鄰域?yàn)镹[v]＝N（v）∪{v}.設(shè)S?V（G），若f是定義在圖G頂點(diǎn)集上的任一實(shí)值函數(shù)，記作f（S）＝∑v∈Sf（v）.

完全多部圖K（n1，…，ni，…，nk），其中k≥3.將其第i部頂點(diǎn)集合記作Vi＝{vi1，vi2，…，vink}.不妨設(shè)n1≤n2≤…≤nk.

若一個(gè)實(shí)值函數(shù)f:V→{0，1，2}滿足條件：每一個(gè)使f（v）＝0的頂點(diǎn)v至少相鄰一個(gè)滿足f（u）＝2的頂點(diǎn)u，則稱f（V）＝Σv∈Vf（v）為圖G的羅馬控制函數(shù).圖的羅馬控制數(shù)定義為是圖G的羅馬控制函數(shù)}.E.J.Cockayne等人在文獻(xiàn)[2]中提出了上述概念，同時(shí)還研究了羅馬控制數(shù)與圖的其他控制數(shù)之間的關(guān)系以及相關(guān)性質(zhì)，并給出了不同條件下羅馬控制數(shù)的上下界.M.Chellali等人在文獻(xiàn)[3]中又進(jìn)一步對(duì)羅馬控制數(shù)與其他控制數(shù)的關(guān)系進(jìn)行了研究，并給出了羅馬控制鏈.

圖G＝（V，E）為簡(jiǎn)單圖，若實(shí)值函數(shù)f:V→{-1，1，2}滿足以下兩個(gè)條件：（i）對(duì)于任意v∈V，均有∑u∈N[v]f（u）≥1成立；（ii）任意v∈V，若f（v）＝-1，則存在一個(gè)與v相鄰的頂點(diǎn)u∈V，滿足f（u）＝2，則稱該函數(shù)為圖G的符號(hào)羅馬控制函數(shù).圖G的符號(hào)羅馬控制數(shù)定義為是圖G的符號(hào)羅馬控制函數(shù)}.若符號(hào)羅馬控制函數(shù)f滿足γSR（G）＝∑v∈Vf（v），則稱函數(shù)f為圖G的γSR（G）-函數(shù).Ahangar等人在文獻(xiàn)[4]中提出了上述概念，并在文獻(xiàn)[4-5]中給出不同條件下圖G符號(hào)羅馬控制數(shù)的上下界以及相關(guān)的臨界圖的刻畫.S.M.Sheikholeslami等人在文獻(xiàn)[6]中對(duì)符號(hào)羅馬控制數(shù)已有的界進(jìn)行了改進(jìn)，得到了更好的上下界，并對(duì)不同條件下有向圖符號(hào)羅馬控制數(shù)的上下界進(jìn)行了研究.文獻(xiàn)[7-10]中還對(duì)其他控制參數(shù)進(jìn)行了研究.

本文主要研究其中當(dāng)k≥3時(shí)，完全多部圖K（n1，…，ni，…，nk）的符號(hào)羅馬控制數(shù)，并給出了完全多部圖符號(hào)羅馬控制數(shù)的準(zhǔn)確值.文中為了證明方便，用G表示k≥3時(shí)的完全多部圖K（n1，…，ni，…，nk），文中所指的均為k≥3的完全多部圖.

1 完全多部圖符號(hào)羅馬控制數(shù)的值及證明

若函數(shù)f為完全多部圖K（n1，…，ni，…，nk）時(shí)的一個(gè)γSR（G）-函數(shù)，令mi＝f（Vi），其中

任意S?V（G），不妨設(shè)S＝{v1，…，vi，…，vk}.定義函數(shù)gi:S→{-1，1，2}如下：

（1）若k為奇數(shù)且k≥3，令g1（v1）＝2，g1（v2）＝-1，g1（v3）＝-1，

（3）若k為偶數(shù)且k≥6，令g3（v1）＝2，g3（v2）＝-1，g3（v3）＝-1，g3（v4）＝2，g3（v5）＝-1，

（4）若k∈{1，3}，令g4（v1）＝1，

（5）若k為奇數(shù)且k≥5，令g5（v1）＝2，g5（v2）＝-1，g5（v3）＝-1，g5（v4）＝2，g5（v5）＝-1，

（6）若k為偶數(shù)，令g6（v1）＝2，g6（v2）＝-1，

（7）若k＝2，令g7（v1）＝1，g7（v2）＝1.

（9）若k為奇數(shù)且k≥3，令g9（v1）＝1，g9（v2）＝1，g9（v3）＝1，

（10）若k為奇數(shù)，令g10（v1）＝-1，

（11）若k為奇數(shù)且k≥7，令g11（v1）＝g11（v2）＝2，g11（vi）＝-1，其中3≤i≤7，

（12）若k為偶數(shù)且k≥4，g12（v1）＝2，g12（vi）＝-1，其中2≤i≤4，

（13）若k為偶數(shù)，令g13（v1）＝g13（v2）＝-1，

（14）若k為奇數(shù)且k≥3，令g14（vi）＝-1，其中1≤i≤3，

其中4≤i≤k.

函數(shù)f＝{f1，f2，…，fk}表示對(duì)完全多部圖K（n1，…，ni，…，nk）的第i部頂點(diǎn)集合采用函數(shù) fi.

引理1：設(shè)f為完全多部圖G＝K（n1，…，ni，…，nk）的一個(gè)γSR（G）-函數(shù)，若對(duì)任意i∈{1，2，…，k}，均有Vf-1∩Vi≠?，則γSR（G）≥3.

證明：對(duì)于任意1≤i≤k，有Vf-1∩Vi≠?.不失一般性，設(shè)f（v11）＝f（v21）＝…＝f（vk1）＝-1，

故（k-1）（m1+m2+m3+…+mk）≥2k.

由于γSR（G）＝m1+m2+m3+…+mk，

引理2：設(shè)f為完全多部圖G＝K（n1，…，ni，…，nk）的一個(gè)γSR（G）-函數(shù)，若存在i∈ {1，2，…，k}，滿足

即任意f（vij）≥1，其中1≤j≤ni，則得證.

定理1：當(dāng)n1＝1時(shí)，完全多部圖K（n1，…，ni，…，nk），其中k≥3，滿足：

（1）γSR（K（n1，…，ni，…，nk））＝2，其中n1＝1；n2≥2.

（2）γSR（K（n1，…，ni，…，nk））＝1，其中n1＝…＝nl＝1；nk-1≥3.

證明：（1）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，若i∈{1，2，…，k}，均有Vi≠?，由引理1得γSR（G）≥3.若i∈{2，…，k}，均有則由引理2可得γSR（G）≥3＞2.不妨設(shè)其中i＝2，…，k.對(duì)于2≤i≤k，不失一般性，令f（v21）＝f（v31）＝…＝f（vk1）＝-1.因?yàn)閒（N[vi1]）≥1，所以：

故（k-2）（m1+m2+m3+…+mk）≥2（k-1）.

又因?yàn)棣肧R（G）＝m1+m2+m3+…+mk，所以

另一方面，按如下方式定義f＝{f1，f2，…，fk}：其中2≤i≤k.易證該函數(shù)為完全多部圖的符號(hào)羅馬控制函數(shù).故γSR（G）≤2.

（2）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，由定義知γSR（G）＝f（N[v11]）≥1.

另一方面：按如下方式定義f＝{f1，f2，…，fk}：

當(dāng)l為奇數(shù)，且l≥3時(shí)：

易證該函數(shù)為完全多部圖的符號(hào)羅馬控制函數(shù)，所以γSR（G）≤1.綜上，γSR（G）＝1.

（3）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，

他撐開一把傘，把愁眉不展的母親從醫(yī)院接回來(lái)。母親告訴他，羅素青的后事還沒辦，家里已經(jīng)鬧得不可開交。她寫了遺囑，出人意外地把遺產(chǎn)全部給了照顧她兩年的保姆，沒有給她的親屬留一分錢。她的親人是她帶大的一個(gè)侄子和兩個(gè)侄女，現(xiàn)在他們憤怒了，不接受這個(gè)事實(shí)。

Vk，則f（N[vk1]）≤-1，矛盾.因此

另一方面，按如下方式定義f＝{f1，f2，…，fk}：

令fi＝g8，其中1≤i≤l；fi＝g13，其中l(wèi)+1≤i≤2l；f2l+1＝g7；

令fi＝g8，其中1≤i≤l；fi＝g13，其中l(wèi)+1≤i≤2l-1；f2l＝g2；

易證該函數(shù)為完全多部圖的符號(hào)羅馬控制函數(shù)，所以γSR（G）≤2.

由定義γSR（G）＝f（N[v11]）≥1.

另一方面，按如下方式定義f＝{f1，f2，…，fk}：（a）k-l＝1.

當(dāng)l為奇數(shù)且l≥3時(shí)：

當(dāng)l為偶數(shù)時(shí)：

若nk為奇數(shù)，令f1＝f2＝g8；

若nk為偶數(shù)，令f1＝g8；f2＝g4

（b）k-l＞1.

當(dāng)l為奇數(shù)且2l-k+1為奇數(shù)時(shí)：

令fi＝g8，其中1≤i≤k-l；其

當(dāng)l為奇數(shù)且2l-k+1為偶數(shù)時(shí)：

令fi＝g8，其中1≤i≤k-l-1；fk-l＝fk-l+1＝g4；i≤l；fi＝g13，其中l(wèi)+1≤i≤k-1；

當(dāng)l為偶數(shù)且2l-k+1為奇數(shù)時(shí)：

令fi＝g8，其中1≤i≤k-l；其中l(wèi)+1≤i≤k-1；

當(dāng)l為偶數(shù)且2l-k+1為偶數(shù)時(shí)：

令fi＝g8，其中1≤i≤k-l-1；fk-l＝fk-l+1＝g4；i≤l；fi＝g13，其中l(wèi)+1≤i≤k-1；

易驗(yàn)證上述情況中函數(shù)f均為該完全多部圖G的符號(hào)羅馬控制函數(shù)，因此γSR（G）≤1.

綜上，γSR（G）＝1.

（4）的證明由（3）的證明類似可得.

定理2：當(dāng)n1＝2時(shí)，完全多部圖K（n1，…，ni，…，nk），其中k≥3，滿足：

（1）γSR（K（n1，…，ni，…，nk））＝2，其中n1＝…＝nl＝2；存在ni，nj，滿足ni≥3，nj≥3且ni≠4，nj≠4.

（2）γSR（K（n1，…，ni，…，nk））＝3，其中n1＝n2＝…＝nk-2＝2；nk-1＝3；nk＝4.

（3）γSR（K（n1，…，ni，…，nk））＝3，其中n1＝…＝nk-2＝2；nk-1＝4；nk＝5，k≥4.

（4）γSR（K（n1，…，ni，…，nk））＝2，其中n1＝…＝nk-2＝2；nk-1＝4；nk≥6，k≥4.

（5）γSR（K（n1，…，ni，…，nk））＝2，其中n1＝…＝nl＝2，l≥2；nl+1＝…＝nk-1＝4，k-l≥3；nk≥5.

（6）γSR（K（n1，…，ni，…，nk））＝3，其中n1＝2；n2＝…＝nk-1＝4；nk≥4.

（7）γSR（K（n1，…，ni，…，nk））＝3，其中n1＝n2＝…＝nk-1＝2；nk≥2.

證明：

（1）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，若i∈{1，2，…，k}，均有Vf-1∩Vi≠?，則由引理1可得γSR（G）≥3＞2.若存在i∈{1，2，…，k}，滿足Vf-1∩Vi＝?，則由引理2可得γSR（G）≥ni≥2.故γSR（G）≥2.

另一方面，按如下方式定義f＝{f1，f2，…，fk}：

令f1＝g7；fi＝g2，其中

易驗(yàn)證該函數(shù)為圖G的符號(hào)羅馬控制函數(shù)，所以γSR（G）≤2.

故γSR（G）＝2.

（2）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，若i∈{1，2，…，k}，均有則由引理1可得γSR（G）≥3.若則由引理2知γSR（G）≥3.若存在i∈{1，2，…，l}，滿足顯然γSR（G）≥3.不妨設(shè)Vk＝?且其中i＝1，2，…，l.若存在i∈{1，2，…，l}，滿足不妨設(shè)則f（v11）＝f（v12）＝1.令顯然γSR（G）≥3，故設(shè)又因?yàn)樗詍k＝f（Vk）＝-1.同理可得mk-1＝0.顯然i∈ {1，2，…，k-2}時(shí)，mi為偶數(shù)，故m為偶數(shù).

由定義γSR（G）＝f（N[v11]）+f（v12）≥2.若等號(hào)成立，則f（N[v11]）＝1，故m+mk-1+mk＝0，m＝1，與m為偶數(shù)矛盾.所以γSR（G）≥3.

另一方面，按如下方式定義f＝{f1，f2，…，fk}：

令f1＝g6；fi＝g2，其中2≤i≤k-2；fk-1＝g4；fk＝g6.易得f為圖G的符號(hào)羅馬控制函數(shù)，所以γSR（G）≤3.

故γSR（G）＝3.

（3）類似于（2）的證明可得γSR（G）≥3.

另一方面，按如下方式定義f＝{f1，f2，…，fk}：

令f1＝g6；fi＝g2，其中2≤i≤k-2；fk-1＝g6；fk＝g5.易驗(yàn)證該函數(shù)為圖G的符號(hào)羅馬控制函數(shù)，故γSR（G）≤3.故γSR（G）＝3.

（4）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，若任意i∈{1，2，…，k}，有≤1成立，則由引理2可知γSR（G）≥2.若i∈{1，2，…，k}，均有則由引理1可得γSR（G）≥3＞2.

因此γSR（G）≥2.

另一方面，按如下方式定義f＝{f1，f2，…，fk}：

令f1＝f2＝g7；fi＝g2，其中3≤i≤k-2；fk-1＝g12；易驗(yàn)證該函數(shù)為圖G的符號(hào)羅馬控制函數(shù)，故γSR（G）≤2.

故γSR（G）＝2.

（5）類似于（4）的證明可得γSR（G）≥2.

另一方面，按如下方式定義f＝{f1，f2，…，fk}：

令f1＝f2＝g7；fi＝g2，其中3≤i≤l；fl+1＝fl+2＝g12；fi＝g2，其中l(wèi)+3≤i≤k-1；

易證該函數(shù)為圖G的符號(hào)羅馬控制函數(shù)，故γSR（G）≤2.

因此γSR（G）＝2.

（6）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，若i∈{1，2，…，k}，均有則由引理1可得γSR（G）≥3.若存在i∈{2，…，k}，滿足則由引理2得γSR（G）≥3.不妨設(shè)其中i＝2，…，k.若易知γSR（G）≥3.若則f（v11）＝f（v12）＝1.對(duì)于i∈{2，…，k}，不失一般性，令f（v21）＝…＝f（vk1）＝-1，分以下情況討論：

由于m1＝2，且由定理2（2）中說(shuō)明可知m2＝m3＝-1，故

由上述3種情況可得γSR（G）≥3.

故γSR（G）＝3.

另一方面：按如下方式定義f＝{f1，f2，…，fk}：

令f1＝f2＝g6；fi＝g2，其中3≤i≤k-1；易驗(yàn)證該函數(shù)為圖G的符號(hào)羅馬控制函數(shù)，故γSR（G）≤3.

綜上，γSR（G）＝3.

（7）設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，

由情況1和情況2得γSR（G）≥3.

另一方面，按如下方式定義f＝{f1，f2，…，fk}：，易驗(yàn)證該函數(shù)為圖G的符號(hào)羅馬控制函數(shù)，所以γSR（G）≤3.

綜上，γSR（G）＝3.

證明：（1）若K（n1，n2，n3）＝K（3，3，4），設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，分以下情況討論：

情況1：任意i∈{1，2，3}，均有Vf-1∩Vi≠?.

由引理1可知γSR（G）≥3.若等號(hào)成立，可得m1+m2＝m2+m3＝m1+m3＝2，即m1＝m2＝m3＝1.不失一般性，設(shè)f（v11）＝f（v21）＝f（v31）＝-1，則f（v12）＝f（v13）＝f（v22）＝f（v23）＝1，矛盾.故γSR（G）≥4.

另一方面：定義函數(shù)f＝{f1，f2，f3}：

令f1＝g8；f2＝g8；f3＝g2.易證該函數(shù)為完全多部圖的符號(hào)羅馬控制函數(shù)，所以γSR（G）≤f（V）＝g8（V1）+g8（V2）+g2（V3）＝2+2+0＝4.

故γSR（G）＝4.

（2）若K（n1，n2，…，nk）?K（3，3，4），設(shè)f為完全多部圖G的一個(gè)γSR（G）-函數(shù)，若i∈{1，2，…，k}，均有則由引理1可得γSR（G）≥3.若存在i∈{1，2，…，k}，滿足則由引理2可得γSR（G）≥ni≥3.故γSR（G）≥3.

另一方面，按照如下方式定義f＝{f1，f2，…，fk}：

①存在i∈{1，2，…，k}，滿足ni＝4.

（i）n1＝…＝nl＝3，其中l(wèi)≥1.

令f1＝g4；fi＝g1，其中2≤i≤l

②任意i∈{1，2，…，k}，均有ni≠4.

（i）n1＝3，n2≥5.

（ii）n1＝…＝ni＝…＝nl＝3，l≥2.

（iii）n1≥5.

易證上述情況下f均為完全多部圖的符號(hào)羅馬控制函數(shù)，故γSR（G）≤3.

綜上，γSR（G）＝3.

[1]BONDY J A，MURTY V S R.Graph theory with applications[M].Amsterdam：Elsevier，1976.

[2]COCKAYNE E J，DREYERJR P A，HEDETNIEMI S M，et al.Roman domination in graphs[J].Discrete Math，2004，278（1/2/3）：11-22.

[3]CHELLALI M，HAYNES T W，HEDETNIEMI S M，et al.A Roman domination chain[J].Graphs Combin，2016，32（1）：79-92.

[4]AHANGAR H A，HENNING M A，LWENSTEIN C，et al.Signed Roman domination in graphs[J].J Comb Optim，2013，308（4）：2313-2318.

[5]AHANGAR H A，HENNING M A，LWENSTEIN C，et al.Signed Roman domination in graphs[J].J Comb Optim，2014，27（2）：241-255.

[6]SHEIKHOLESLAMI S M，VOLKMANN L.Signed Roman domination in digraphs[J].J Comb Optim，2015，30（3）：456-467.

[7]HENNING M A，VOLKMAN L.Signed Roman k-domination in graphs[J].Graphs Combin，2016，32（1）：175-190.

[8]張立賢.圖的參數(shù)控制研究[D].浙江：浙江師范大學(xué)，2015.

[9]張立賢，呂新中.圖的逆羅馬控制數(shù)[J].蘭州文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2015，29（1）：5-11.

[10]曹惠萍.若干圖類的全符號(hào)控制數(shù)的研究[D].大連：大連海事大學(xué)，2016.

Signed Roman Domination of Multi-Partite Graph

YIN Kai,CHEN Xuegang
（Institute of Mathematics and Physics,North China of Electric Power University,Beijing,102200）

A signed Roman domination function,of a simple undirected graph G＝（V，E）is a function f:V→{-1，1，2}satisfying the conditions that（i）∑u∈N[v]f（u）≥1 for any v∈V,and（ii）every vertex v for which f（v）＝-1 is adjacent to a vertex u for which f（u）＝2.The signed roman domination number of G isis the signed roman domination of G}.In this paper,we compute the exact values of the signed roman domination numbers of complete multi-partite graph when k＞＝3,through classification the vertex of G.

complete multi-partite graph；signed roman domination function；signed roman domination number.

1001-4217（2017）04-0025-10

2017-02-26

尹凱（1992—），女，山西晉中，碩士研究生，研究方向：圖論與組合優(yōu)化.E-mail：huadianyinkai@163.com

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助（2016MS66）

O 157.5

A