两类特殊图的符号控制数

徐荣贵, 孔祥阳, 张　磊

(四川工程职业技术学院 基础教学部,四川 德阳 618000)



两类特殊图的符号控制数

徐荣贵, 孔祥阳, 张磊

(四川工程职业技术学院 基础教学部,四川 德阳 618000)

摘要：图的符号控制理论与局部占优有关，而一般图的符号控制数难以给出具体的计算公式，同时，在图的应用过程中，某些特殊图的使用比较常见，因此，得到这些特殊图的符号控制数是十分必要的.通过对两类特殊图的符号控制数进行研究，给出它们的符号控制数的表达式.

关键词：符号控制函数；符号控制数；度

0引言

文中符号和术语若无特别说明，表示与文献[1]相同.文献[2-5]给出了相关的较新的结果.

对于图G=(V,E)的一个顶点v∈V，集合NG(v)={u|uv∈E(G)}称为v在图G中的开邻域.顶点v在G中的度是指点v在G中的邻点的个数，记作dG(v)=|NG(v)|，并记Δ=Δ(G)为图G的最大度,δ=δ(G)为图G的最小度，为了叙述方便，将以上这些符号简记为d(v)、N(v)、N[v].

1相关定义

定义2[7]由两个回路Cn恰有一个公共点所组成的图记作D2,n.

图1为D2,8及其编号规则(在每个Cn上从v0开始按逆时针方向进行编号).

图1　D2,8及其编号Fig.1　D2,8 and its number

定义3[7]顺序有一个公共点的m个C4的并图记作Fm,4.

图2为F4,4及其编号规则.

2主要定理及证明

定理1对于图D2,n，有

图2　F4,4及其编号Fig.2　F4,4 and its number

(1)当n≡0(mod 3)时，令n=3k,k∈N+，则

在V(D2,n)上定义函数f如下,

(2)当n≡1(mod3)时，令n=3k+1,k∈N+，于是

此等号成立的条件是f(v0)=+1.如果f(v0)=-1，则必存在某个顶点w，使得f[w]=-1，与定义1矛盾.在V(D2,n)上定义函数f如下,

在V(D2,n)上定义函数f如下,

定理2对于图Fm,4，有γs(Fm,4)=m+1.

证明根据Fm,4的结构特征可以看出，每个C4上至多有一个顶点取-1，因此γs(Fm,4)≥m+1.下面在V(Fm,4)上定义一个函数f如下,

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

参考文献

[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]高扬,任媛. n·Pm的符号控制数[J].内蒙古民族大学学报:自然科学版,2012,28(2):139-141.

[4]孔祥阳,徐保根.关于Double图的符号控制数[J].河南科技学院学报:自然科学版,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]马克杰.优美图[M].北京:北京大学出版社,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

中图分类号：O157.5

文献标识码：A

文章编号：1007-0834(2015)02-0016-03

doi：10.3969/j.issn.1007-0834.2015.02.005

作者简介：徐荣贵(1965—)，男，四川德阳人，四川工程职业技术学院基础教学部讲师.

收稿日期：2015-02-28