完全多部圖的符號羅馬控制數

尹 凱，陳學剛

（華北電力大學數理學院，北京 102200）

完全多部圖的符號羅馬控制數

尹 凱，陳學剛

（華北電力大學數理學院，北京 102200）

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

完全多部圖；符號羅馬控制函數；符號羅馬控制數

0 引言

文中所指的圖均為簡單無向圖，文中符號和術語同文獻[1].

設圖G＝（V，E）是一個簡單無向圖，V（G）和E（G）分別是圖G的頂點集和邊集.令頂點v的開鄰域N（v）是指圖G中所有與v相鄰的點的集合.頂點v的閉鄰域為N[v]＝N（v）∪{v}.設S?V（G），若f是定義在圖G頂點集上的任一實值函數，記作f（S）＝∑v∈Sf（v）.

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

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

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

本文主要研究其中當k≥3時，完全多部圖K（n1，…，ni，…，nk）的符號羅馬控制數，并給出了完全多部圖符號羅馬控制數的準確值.文中為了證明方便，用G表示k≥3時的完全多部圖K（n1，…，ni，…，nk），文中所指的均為k≥3的完全多部圖.

1 完全多部圖符號羅馬控制數的值及證明

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

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

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

（3）若k為偶數且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為奇數且k≥5，令g5（v1）＝2，g5（v2）＝-1，g5（v3）＝-1，g5（v4）＝2，g5（v5）＝-1，

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

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

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

（10）若k為奇數，令g10（v1）＝-1，

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

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

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

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

其中4≤i≤k.

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

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

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

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

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

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

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

定理1：當n1＝1時，完全多部圖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）設f為完全多部圖G的一個γSR（G）-函數，若i∈{1，2，…，k}，均有Vi≠?，由引理1得γSR（G）≥3.若i∈{2，…，k}，均有則由引理2可得γSR（G）≥3＞2.不妨設其中i＝2，…，k.對于2≤i≤k，不失一般性，令f（v21）＝f（v31）＝…＝f（vk1）＝-1.因為f（N[vi1]）≥1，所以：

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

又因為γSR（G）＝m1+m2+m3+…+mk，所以

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

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

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

當l為奇數，且l≥3時：

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

（3）設f為完全多部圖G的一個γSR（G）-函數，

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

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

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

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

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

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

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

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

當l為奇數且l≥3時：

當l為偶數時：

若nk為奇數，令f1＝f2＝g8；

若nk為偶數，令f1＝g8；f2＝g4

（b）k-l＞1.

當l為奇數且2l-k+1為奇數時：

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

當l為奇數且2l-k+1為偶數時：

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

當l為偶數且2l-k+1為奇數時：

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

當l為偶數且2l-k+1為偶數時：

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

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

綜上，γSR（G）＝1.

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

定理2：當n1＝2時，完全多部圖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）設f為完全多部圖G的一個γSR（G）-函數，若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，其中

易驗證該函數為圖G的符號羅馬控制函數，所以γSR（G）≤2.

故γSR（G）＝2.

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

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

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

令f1＝g6；fi＝g2，其中2≤i≤k-2；fk-1＝g4；fk＝g6.易得f為圖G的符號羅馬控制函數，所以γ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.易驗證該函數為圖G的符號羅馬控制函數，故γSR（G）≤3.故γSR（G）＝3.

（4）設f為完全多部圖G的一個γSR（G）-函數，若任意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；易驗證該函數為圖G的符號羅馬控制函數，故γ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+3≤i≤k-1；

易證該函數為圖G的符號羅馬控制函數，故γSR（G）≤2.

因此γSR（G）＝2.

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

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

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

故γSR（G）＝3.

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

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

綜上，γSR（G）＝3.

（7）設f為完全多部圖G的一個γSR（G）-函數，

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

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

綜上，γSR（G）＝3.

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

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

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

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

令f1＝g8；f2＝g8；f3＝g2.易證該函數為完全多部圖的符號羅馬控制函數，所以γ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），設f為完全多部圖G的一個γSR（G）-函數，若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≥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均為完全多部圖的符號羅馬控制函數，故γ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]張立賢.圖的參數控制研究[D].浙江：浙江師范大學，2015.

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

[10]曹惠萍.若干圖類的全符號控制數的研究[D].大連：大連海事大學，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—），女，山西晉中，碩士研究生，研究方向：圖論與組合優化.E-mail：huadianyinkai@163.com

中央高校基本科研業務費專項資金資助（2016MS66）

O 157.5

A