图的笛卡尔乘积的控制数与罗马控制数

《图的笛卡尔乘积的控制数与罗马控制数》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得安徽大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：裴杀17．丹签字日期：珈f≯年f月?2一日学位论文版权使用授权书本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘

2、，允许论文被查阅和借阅。本人授权安徽大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：袈禾1】再导师签名：签字日期：诩f争年易月J1日签字日期：摘要IIIIIIIIIIIIIIIMIIUIIfY2579767对任意图G，其顶点集的非空子集JD是一个控制集，若对每个”∈矿(G)一D，它的邻集与D的交集非空．图G的最小控制集中的顶点数是G的控制数，y(G)表示图G的控制数．GoH是图G和图何的笛

3、卡尔乘积图，在此笛卡尔乘积图中点(Ⅳ，v)与(”’，’，’)有边相连，当且仅当v=v’_Kuu’∈E(G)，或者“=Ⅳ’且w’∈E(H)．本文首先给出路与圈笛卡尔乘积图C卅口只沏=2，3，4)与己口G(珊=2，3，4)控制数的精确值．函数厂：y(G)斗{o，1，2)表示图G的罗马控制函数，对每个点甜∈Vo都与圪中的点有边相连，其中¨=铷∈矿(G)I厂@)=f)．／(y(G))=∑删f6)厂@)表示函数．厂的权重，图G的罗马控制数％(G)是图G所有罗马控制函数f的最小权重．函数厂是‰(G)一函数，若它是一个罗

4、马控制函数且厂(y(G))=YR(G)．1963年，Vizing提出有关笛卡尔乘积图控制数的著名V'ming猜想7(GDH)≥y(G)y(H)，引起了很大的关注，并得出了许多与Vizing猜想形式类似的结果，本文另一个重要结果是用罗马控制给出了与Ⅵzing猜想有关的z(GoH)的一个下界：对任意的无孤立点图G和H，有y(G口H)>4zR(G)7凡(H)成立·最后得到了与Vi：dmg猜想有关‰(G口日)的一个下界：对任意的无孤立点图G和图H，有‰(G口日)≥7(G)，(日)+111in{厂(G)，，(日)}成

5、立，为后续罗马控制数的研究有更进一步的帮助．本文的组织结构为：第一，二章先介绍控制数和Vizing猜想的研究背景及国内外的研究现状，介绍了图论中的基本概念及专业基础知识．第三，四，五章分别介绍本文的三个主要研究成果．第六章总结全文的主要研究成果，并在此基础上指明了我们可以进一步研究的方向．关键词：笛卡尔乘积；控制数；罗马控制数；Vizing猜想AbstractForanygraphG，anonemptysubsetofitsvertexsetisadominationset，ifeveryvertexin矿

6、(G)一D，N(x)ND≠f2j．ThedominationnumberofagraphGistheminimumconcentrationofdominationset．Lety(G)bethedominationnumberofagraphGandGcJHdenotetheCartesianproductofgraphsGandH．IntheCartesianproductofgraphsGandH，(Ⅳ，V)and(”’，V’)areadjacentifandonlyif1，=v’，UU’∈E(G)o

7、ru=”7，w’∈E(H)．Inthispaper,wedeterminethedominationnumberoftheCartesianproductsofC卅口只(雕=2，3，4)and己口G(m=2，3，4)．Afunctionf：y(G)j{0,1，2}isaRomandominatingfunction0U)F)ifforanyvertexⅣ∈z0musthaveⅣGm)n吒≠o，whereE=缸∈v(a)l厂@)=j>．Theweightoffisgivenby／(矿(G))=∑)mVCG)厂

8、(“)．TheRomand。minati。nnumberrAG)1stheiTlJninlunlweightamongallRDFfSofG，andwepointthatafunctionfisarAG)一functionifitisallRDFand／(y(G))=‰(G)．In1963，Vizingmadethewell．knownconjectureonthedominationinCartesianpro