周　穎，葉淼林

(安慶師范大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

?

圖的符號(hào)控制數(shù)的一些上、下界

周穎，葉淼林

(安慶師范大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院，安徽 安慶 246133)

摘要：根據(jù)符號(hào)控制數(shù)的定義，推廣了一些特殊圖的符號(hào)控制數(shù)的上、下界及路與路的積圖的符號(hào)控制數(shù)。

關(guān)鍵詞：正則圖；符號(hào)控制數(shù)；積圖

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.002

本文所討論的圖均為無向簡(jiǎn)單圖。設(shè)G=[V(G),E(G)]為n階無向簡(jiǎn)單圖，u的鄰點(diǎn)集合記為N(u)，其中u點(diǎn)的閉鄰域?yàn)镹[u]={u}∪N(u)，N(u)的頂點(diǎn)個(gè)數(shù)稱為u在G中的度數(shù)，記為dG(v)，簡(jiǎn)記為d(v)，各個(gè)頂點(diǎn)的度數(shù)都相等的圖稱為正則圖。

一個(gè)雙值函數(shù)f∶V→{1,-1}，如果對(duì)任意u∈V，均有

成立，則稱f為圖G的一個(gè)符號(hào)控制函數(shù)。

圖G的符號(hào)控制數(shù)定義為γs(G)=min{f(V)|f為圖G的一個(gè)符號(hào)控制函數(shù)}，并且記f[V]=f(N[V])。設(shè)G1=(V1,E1)和G2=(V2,E2)為兩個(gè)圖，則其積圖G1×G2定義為V(G1×G2)=V1×V2,E(G1×G2)={(u1,v1)(u2,v2)|u1=u2且v1與v2在G2中鄰接或者v1=v2且u1與u2在G1中鄰接}。

下面給出本文的主要結(jié)論。

證明由圖G為2k+1正則圖，則對(duì)任意

v∈V均有f[v]=f(N[v])≥2，而

(2k+2)f[V]，

故(2k+2)f[V]≥2n，即

這個(gè)結(jié)論比引理1精確。

定義圖G的懸掛圖為在G的頂點(diǎn)vi(i=1,2,…,n)上懸掛ni(ni≥1)個(gè)頂點(diǎn)所得的圖。由定義可知一個(gè)圖是懸掛圖的充要條件是圖中頂點(diǎn)要么度為1，要么有度為1的鄰點(diǎn)。

定理2n階圖G的符號(hào)控制數(shù)γs(G)=n的充要條件為G是某個(gè)圖H的懸掛圖。

證明充分性：

當(dāng)G為某個(gè)圖H的懸掛圖時(shí)，記所有懸掛點(diǎn)為S，則對(duì)?v∈S，均有f[v]≥1，故懸掛點(diǎn)v及其鄰點(diǎn)必須賦值為1，即γs(G)=n。

必要性：

若G不是懸掛圖，則G中至少有一點(diǎn)v∈V(G)，使得當(dāng)u∈N[v]時(shí)，d(u)≥2。若此時(shí)給v點(diǎn)賦值-1，其余頂點(diǎn)都賦值1，即可得一符號(hào)控制函數(shù)使得γs(G)≤n-2，此時(shí)與γs(G)=n矛盾，故v點(diǎn)不可賦值為-1，即d(v)<2，因此G必為懸掛圖。

證明設(shè)p2=ab，pn=1,2,…,n，p2×pn的頂點(diǎn)記為ai,bj,i,j=1,2,…,n。邊集為{aiai+1|

i=1,2,…,n-1}∪{bibi+1|i=1,2,…,n-1}∪{aibi|i=1,2,…,n}。

當(dāng)n=2時(shí)，p2×p2為一四邊形，此時(shí)最多有一個(gè)頂點(diǎn)賦值為-1，

γs(p2×p2)=3-1=2，

定理3成立。

當(dāng)n≥3時(shí)，

(1)p2×pn中僅有a1,b1,an,bn為2度頂點(diǎn)，任意符號(hào)控制函數(shù)f都有f[ai]≥1，f[bi]≥1,

i=1,…，n。a2,a3,…,an-1和b2,b3,…,bn-1均為3度頂點(diǎn)，對(duì)任意符號(hào)控制函數(shù)f都有f[ai]≥2，f[bi]≥2,i=2,3,…,n-1。

(2)對(duì)任意頂點(diǎn)v，在N[v]中至多只能有一個(gè)頂點(diǎn)u賦值f(u)=-1?；谝陨蟽牲c(diǎn)，p2×p4中至多只能有兩點(diǎn)賦值為-1，f(V)≥6-2=4，而令f(a1)=f(b3)=-1，其余點(diǎn)賦值為1或f(a1)=f(b4)=-1，其余點(diǎn)賦值為1或f(b1)=f(a3)=-1，其余點(diǎn)賦值為1或f(b1)=f(a4)=-1，其余點(diǎn)賦值為1，均可使得p2×p4的賦值總和為4，故γs(p2×p4)=4，定理3成立。

當(dāng)n=4k+1時(shí)，令f(a4i+1)=-1,i=1,2,…,k， f(b4i+3)=-1,i=1,2,…,k-1，其余點(diǎn)v均令f(v)=1，則

f(V)=2(4k+1)-2(k+k-1)=

因此時(shí)p2×pn中均是等式出現(xiàn)，故f是最小符號(hào)控制。

參考文獻(xiàn):

[1] 裴利丹，連小娟，潘向峰. 路與圈的笛卡爾乘積的控制數(shù)[J]. 合肥學(xué)院報(bào)(自然科學(xué)版), 2013, 23(3): 24-28.

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

[3]張先迪, 李正良. 圖論及其應(yīng)用[M]. 北京: 高等教育出版社, 2005.

[4] Gravier S,Khelladi A.On the domination number of cross products of graph[J]. Discrete Math,1995, 145: 273-277.

Upper and Lower Bounds of the Singed Domination in Graphs

ZHOU Ying,YE Miao-lin

(School of Mathematics and Computational Science, Anqing Normal University, Anqing, Anhui 246133, China)

Abstract:Based on the definition of signed domination number, this paper extends some special graphs signed domination number of upper and lower bound and signed domination number of product of path.

Key words:regular graph; singed domination; Cartesian

* 收稿日期：2015-11-11

作者簡(jiǎn)介：周穎，女，安徽樅陽人，安慶師范大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院碩士研究生，研究方向?yàn)榭刂茍D論。 E-mail: 1056363202@qq.com

中圖分類號(hào)：O231

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1007-4260(2016)02-0004-02

網(wǎng)絡(luò)出版時(shí)間：2016-06-08 12:57網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.002.html