论文部分内容阅读
对任意图G,其顶点集的非空子集D是一个控制集,若对每个u∈V(G)-D,它的邻集与D的交集非空.图G的最小控制集中的顶点数是G的控制数,γ(G)表示图G的控制数.G□H是图G和图H的笛卡尔乘积图,在此笛卡尔乘积图中点(u,v)与(u,v)有边相连,当且仅当v=v且uu∈E(G),或者u=u且vv∈E(H).本文首先给出路与圈笛卡尔乘积图Cm□Pn(m=2,3,4)与Pm□Cn(m=2,3,4)控制数的精确值. 函数f: V(G)→{0,1,2}表示图G的罗马控制函数,对每个点u∈V0都与V2中的点有边相连,其中Vi={u∈V(G)|f(u)=i}.f(V(G))=∑u∈V(G)f(u)表示函数f的权重,图G的罗马控制数γR(G)是图G所有罗马控制函数f的最小权重.函数f是γR(G)-函数,若它是一个罗马控制函数且f(V(G))=γR(G).1963年,Vizing提出有关笛卡尔乘积图控制数的著名Vizing猜想γ(G□H)≥γ(G)γ(H),引起了很大的关注,并得出了许多与Vizing猜想形式类似的结果,本文另一个重要结果是用罗马控制给出了与Vizing猜想有关的γ(G□H)的一个下界:对任意的无孤立点图G和H,有γ(G□H)≥1/4γR(G)γR(H)成立. 最后得到了与Vizing猜想有关γR(G□H)的一个下界:对任意的无孤立点图G和图H,有γR(G□H)≥γ(G)γ(H)+ min{γ(G),γ(H)}成立,为后续罗马控制数的研究有更进一步的帮助. 本文的组织结构为:第一,二章先介绍控制数和Vizing猜想的研究背景及国内外的研究现状,介绍了图论中的基本概念及专业基础知识.第三,四,五章分别介绍本文的三个主要研究成果.第六章总结全文的主要研究成果,并在此基础上指明了我们可以进一步研究的方向.