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

徐榮貴, 孔祥陽(yáng), 張　磊

(四川工程職業(yè)技術(shù)學(xué)院 基礎(chǔ)教學(xué)部,四川 德陽(yáng) 618000)

?

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

徐榮貴, 孔祥陽(yáng), 張磊

(四川工程職業(yè)技術(shù)學(xué)院 基礎(chǔ)教學(xué)部,四川 德陽(yáng) 618000)

摘要：圖的符號(hào)控制理論與局部占優(yōu)有關(guān)，而一般圖的符號(hào)控制數(shù)難以給出具體的計(jì)算公式，同時(shí)，在圖的應(yīng)用過程中，某些特殊圖的使用比較常見，因此，得到這些特殊圖的符號(hào)控制數(shù)是十分必要的.通過對(duì)兩類特殊圖的符號(hào)控制數(shù)進(jìn)行研究，給出它們的符號(hào)控制數(shù)的表達(dá)式.

關(guān)鍵詞：符號(hào)控制函數(shù)；符號(hào)控制數(shù)；度

0引言

文中符號(hào)和術(shù)語(yǔ)若無特別說明，表示與文獻(xiàn)[1]相同.文獻(xiàn)[2-5]給出了相關(guān)的較新的結(jié)果.

對(duì)于圖G=(V,E)的一個(gè)頂點(diǎn)v∈V，集合NG(v)={u|uv∈E(G)}稱為v在圖G中的開鄰域.頂點(diǎn)v在G中的度是指點(diǎn)v在G中的鄰點(diǎn)的個(gè)數(shù)，記作dG(v)=|NG(v)|，并記Δ=Δ(G)為圖G的最大度,δ=δ(G)為圖G的最小度，為了敘述方便，將以上這些符號(hào)簡(jiǎn)記為d(v)、N(v)、N[v].

1相關(guān)定義

定義2[7]由兩個(gè)回路Cn恰有一個(gè)公共點(diǎn)所組成的圖記作D2,n.

圖1為D2,8及其編號(hào)規(guī)則(在每個(gè)Cn上從v0開始按逆時(shí)針方向進(jìn)行編號(hào)).

圖1　D2,8及其編號(hào)Fig.1　D2,8 and its number

定義3[7]順序有一個(gè)公共點(diǎn)的m個(gè)C4的并圖記作Fm,4.

圖2為F4,4及其編號(hào)規(guī)則.

2主要定理及證明

定理1對(duì)于圖D2,n，有

圖2　F4,4及其編號(hào)Fig.2　F4,4 and its number

(1)當(dāng)n≡0(mod 3)時(shí)，令n=3k,k∈N+，則

在V(D2,n)上定義函數(shù)f如下,

(2)當(dāng)n≡1(mod3)時(shí)，令n=3k+1,k∈N+，于是

此等號(hào)成立的條件是f(v0)=+1.如果f(v0)=-1，則必存在某個(gè)頂點(diǎn)w，使得f[w]=-1，與定義1矛盾.在V(D2,n)上定義函數(shù)f如下,

在V(D2,n)上定義函數(shù)f如下,

定理2對(duì)于圖Fm,4，有γs(Fm,4)=m+1.

證明根據(jù)Fm,4的結(jié)構(gòu)特征可以看出，每個(gè)C4上至多有一個(gè)頂點(diǎn)取-1，因此γs(Fm,4)≥m+1.下面在V(Fm,4)上定義一個(gè)函數(shù)f如下,

此時(shí)f(V(Fm,4))=m+1，所以有γs(Fm,4)=m+1.

參考文獻(xiàn)

[1]DUNBARJE,HEDETNIEMIST,HENNINGMA,etal.Signeddominationingraphs[J].GraphTheory,CombinatoricsandApplications, 1995(1): 311-322.

[2]YINGZHENG,JIANXINWANG,QILONGFENG,etal.FPTResultsforsigneddomination[J].TheoryandApplicationsofModelsofComputationLectureNotesinComputerScience, 2012, 7287:572-583.

[3]高揚(yáng),任媛. n·Pm的符號(hào)控制數(shù)[J].內(nèi)蒙古民族大學(xué)學(xué)報(bào):自然科學(xué)版,2012,28(2):139-141.

[4]孔祥陽(yáng),徐保根.關(guān)于Double圖的符號(hào)控制數(shù)[J].河南科技學(xué)院學(xué)報(bào):自然科學(xué)版,2012,40(4):54-57.

[5]HAYNESTW,HEDETNIEMIST,SLATERPJ.Dominationingraphs:Advancedtopics[M].NewYork:MarcelDekker, 1998.

[6]ZHANGZHONGFU,XUBAOGEN,etal.Anoteonthelowerboundsofthesigneddominationnumberofagraph[J]．DiscreteMathematics,1999,195:295-298．

[7]馬克杰.優(yōu)美圖[M].北京:北京大學(xué)出版社,1991.

On Signed Domination Numbers of Two Kinds of Special Graphs

XU Rong-gui, KONG Xiang-yang, ZHANG Lei

(MinistryofBasicEducation,SichuanEngineeringTechnicalCollege,Deyang618000,China)

Abstract:The signed domination theory is related to the local priority problem, and the use of some special graphs is frequent in the applications, so it’s very necessary to obtain the signed domination numbers of such special graphs. Through the study of signed domination numbers of several kinds of special graphs, the expressions of signed domination numbers are given.

Key words:signed dominating function; signed domination number; degree

中圖分類號(hào)：O157.5

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

文章編號(hào)：1007-0834(2015)02-0016-03

doi：10.3969/j.issn.1007-0834.2015.02.005

作者簡(jiǎn)介：徐榮貴(1965—)，男，四川德陽(yáng)人，四川工程職業(yè)技術(shù)學(xué)院基礎(chǔ)教學(xué)部講師.

收稿日期：2015-02-28