兩類圖的符號控制數

閆云娟，徐保根，馮大一

（華東交通大學理學院，江西 南昌330013）

兩類圖的符號控制數

閆云娟，徐保根，馮大一

（華東交通大學理學院，江西 南昌330013）

設圖 G=（V，E）為一個圖，一個雙值函數如果對任意的 v∈V,均有 f（N［v］）≥1成立，則稱 f為圖 G 的一個符號控制函數,圖 G 的符號控制數定義為 γs（G）＝min｛f（V）｜f為圖 G 的一個符號控制函數｝。C（n，m）=CnPm表示Pm的一個端點與Cn中的一個點粘接（重合）而成的圖；C（n，m，n）=CnPmCn表示Pm的兩個端點分別粘接一個Cn而成的圖。 文章確定了 C（n，m）和 C（n，m，n）的符號控制數。

圖；符號控制函數；符號控制數

1 相關定義及推論

設圖G=（V，E）,對于任意頂點v∈V,在G中與v點相鄰的所有頂點的集合稱為v在圖G中的開鄰域，記作 NG（v）=｛u｜uv∈E（G）｝，v 點在圖 G 中的閉鄰域記為 NG［v］＝NG（v）∪｛v｝。 頂點 v 在 G 中的度是指 v 在 G中鄰點的個數，記作，不引混亂時，分別簡記為 N（v），N［v］和 d［v］。 Cn和 Pn分別表示 n 階圈和路。

對于圖 G=（V，E），定義一個函數 f：V→R 和 G 的一個子集

J E Dunbar[1]等在1995年首次提出了圖的符號控制的概念，這很快受到了學者們的廣泛關注。

定義 1[2-4]設圖 G=（V，E）為一個圖，一個雙值函數 f：V→｛1，1｝，如果對任意的 v∈V，均有 f（N［v］）≥1成立，則稱f為圖G的一個符號控制函數，圖G的符號控制數定義為：γs（G）＝min｛f（V）｜f為圖G的一個符號控制函數｝，并將使得γs（G）＝f（V）的符號控制函數稱f為圖G的一個最小符號控制函數。

引理 1[5-7]設 f為圖 G 的一個符號控制函數，v∈V,當 d（v）為奇數時 f（N［v］）≥2，當 d（v）為偶數時 f（N［v］）≥1。

引理 2[8-9]設 n≥3，圈 Cn的最小控制數

定義2 由Pm的一個端點與Cn中的一個點粘接（重合）而成的圖形稱為氣球圖記為C（n，m）=CnPm，Pm與Cn的粘接點記為v2（um）；在Cn上從v1開始逆時針編號，在Pm上從u1開始從左到右編號。

定義3 由Pm的兩個端點分別粘接一個Cn而成的圖形稱為啞鈴圖記為C （n，m，n）=CnPmCn，左側Cn和 Pm的粘接點記為v2（w1），右側 Cn和 Pm的粘接點記為 u2（wm）；在左側 Cn上從 v1開始逆時針編號，在右側Cn上u1從開始順時針編號，在Pm上從w1開始從左到右編號。

2 主要結論及證明

證明 設圈Cn和路Pm的粘接點為v2=um，圈Cn上共有n個點，路Pm上有m個點；設f為圖G1的一個最小符號控制函數，則 γs（G）=f（V），顯然 f（u1）=f（u2）=1，否則與 f為圖 G1的一個最小符號控制函數矛盾。

1） 當 m=3t時。

② n＝3k+1 。 因為 d（v2）=3，必有 f（N v2[]）≥2，故 v2閉鄰域內對應的最小符號控制函數值為“-1”的點至多只有一個，分以下兩種情況討論：

情況2 若v2閉鄰域內標號為“-1”的點不在圈上。則必有f（v2）=1。

③n＝3k+2。由②同理：

情況 1 不妨設 f（vn）＝f（v1）=f（v2）=1 。

證明 由Pm的兩個端點分別粘接一個Cn而成的圖形稱為啞鈴圖記為C（n，m，n）＝CnPmCn，左側Cn和Pm的粘接點記為 v2（w1），右側 Cn和 Pm的粘接點記為設 f為圖 G2的一個最小符號控制函數，則 γs（G）=f（V）。

1） 當 n=3l時 。

[1]DUNBAR J E，HEDETNIEMI S T，HENNING M A，et al.Signed domination in graphs[J].J Shanghai Univ，2006（10）：4-8.

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

[3]HAYNES T W，HEDETNIEMI S T，SLATER P J.Signed，domination in graphs[M].New york：Marcel Dekker Inc，1998.

[4]徐保根.圖的控制理論[M].北京：科學出版社，2008.

[5]徐保根.圖的控制與染色理論[M].武漢：華中科技大學出版社，2013.

[6]徐保根.關于圖的符號星控制數[J].華東交通大學學報，2004，21（4）：116-118.

[7]徐保根.兩類圖的符號星控制數[J].華東交通大學學報，2005，22（4）：146-148.

[8]徐保根.偶圖符號控制數的下界[J].華東交通大學學報，2014，31（6）：93-95.

[9]徐榮貴，孔祥陽，徐保根.兩類特殊圖的控制數[J].江西科學，2015，33（1）：57-58.

On Signed Domination Numbers for Two Classes of Graphs

Yan Yunjuan，Xu Baogen，Feng Dayi
（College of Science,East China Jiaotong University,Nanchang 330013,China）

LetG=（V，E） be a graph,a functionf：V→{1，－1}is said to be a signed dominating function(SDF);when S?V,there is the followingf（S）holds for all v∈V,the signed domination number is γs（G）＝min ｛f （V）｜f is an SDF of G}.In this paper,the signed domination problem for two classes of special graphs is researched and the signed domination numbers ofC（n，m）=CnPmandC（n，m，n）=CnPmCnare obtained.

graph;signed dominating function;signed domination number

（責任編輯 姜紅貴）

O157.5

A

1005-0523（2017）06-0109-07

2017－06－22

國家自然科學基金（11361024）；江西省高校科技落地計劃項目（KJLD12067）；江西省自然科學基金項目（20171BAB201009）

閆云娟（1977—），女，講師，研究方向為圖與網絡。