閆云娟，徐保根，馮大一

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

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

閆云娟，徐保根，馮大一

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

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

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

1 相關(guān)定義及推論

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

對(duì)于圖 G=（V，E），定義一個(gè)函數(shù) f：V→R 和 G 的一個(gè)子集

J E Dunbar[1]等在1995年首次提出了圖的符號(hào)控制的概念，這很快受到了學(xué)者們的廣泛關(guān)注。

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

引理 1[5-7]設(shè) f為圖 G 的一個(gè)符號(hào)控制函數(shù)，v∈V,當(dāng) d（v）為奇數(shù)時(shí) f（N［v］）≥2，當(dāng) d（v）為偶數(shù)時(shí) f（N［v］）≥1。

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

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

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

2 主要結(jié)論及證明

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

1） 當(dāng) m=3t時(shí)。

② n＝3k+1 。 因?yàn)?d（v2）=3，必有 f（N v2[]）≥2，故 v2閉鄰域內(nèi)對(duì)應(yīng)的最小符號(hào)控制函數(shù)值為“-1”的點(diǎn)至多只有一個(gè)，分以下兩種情況討論：

情況2 若v2閉鄰域內(nèi)標(biāo)號(hào)為“-1”的點(diǎn)不在圈上。則必有f（v2）=1。

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

情況 1 不妨設(shè) f（vn）＝f（v1）=f（v2）=1 。

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

1） 當(dāng) n=3l時(shí) 。

[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].北京：科學(xué)出版社，2008.

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

[6]徐保根.關(guān)于圖的符號(hào)星控制數(shù)[J].華東交通大學(xué)學(xué)報(bào)，2004，21（4）：116-118.

[7]徐保根.兩類圖的符號(hào)星控制數(shù)[J].華東交通大學(xué)學(xué)報(bào)，2005，22（4）：146-148.

[8]徐保根.偶圖符號(hào)控制數(shù)的下界[J].華東交通大學(xué)學(xué)報(bào)，2014，31（6）：93-95.

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

On Signed Domination Numbers for Two Classes of Graphs

Yan Yunjuan，Xu Baogen，F(xiàn)eng 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

（責(zé)任編輯 姜紅貴）

O157.5

A

1005-0523（2017）06-0109-07

2017－06－22

國(guó)家自然科學(xué)基金（11361024）；江西省高?？萍悸涞赜?jì)劃項(xiàng)目（KJLD12067）；江西省自然科學(xué)基金項(xiàng)目（20171BAB201009）

閆云娟（1977—），女，講師，研究方向?yàn)閳D與網(wǎng)絡(luò)。