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

来源 :安徽大学 | 被引量 : 0次 | 上传用户:chunhuaqiuyue
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
对任意图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猜想的研究背景及国内外的研究现状,介绍了图论中的基本概念及专业基础知识.第三,四,五章分别介绍本文的三个主要研究成果.第六章总结全文的主要研究成果,并在此基础上指明了我们可以进一步研究的方向.
其他文献
摘 要:随着我国股指期货2009 年4 月16 日开始上市交易,我国自此摆脱了股票市场"单边市"的情形。但在交易过程中也暴露出诸多潜在的风险,本文针对我国股指期货市场近年来已经存在和可能存在的风险加以分析,并提供相应的对策和预防方案。  关键词:股指期货、风险管理、风险    一、股指期货风险的定义与分类:  股指期货的风险主要指的是股指期货的参与者在股指期货的操作过程中由于收益的不确定间接或直
本论文主要利用距离几何理论研究了体积在两个单形间的推广和利用“偏正”度量理论研究单形外接球半径的两个不等式和切点单形的两个不等式,并给出他们稳定性版本。全文共分四
当今时代,网络与人们的生产生活息息相关,特别是因特网的发展使得我们的生活变得方便快捷,这就需要我们深入全面的分析和研究复杂网络,使其更好地为人类服务。Multi-Agent系统作
函数方程的稳定性问题最初是在1940年由数学家S.Ulam提出的,研究的问题具体为:设G是群,G(·,ρ)是度量群,对(∨)ε>0,(E)δ>0,使得对(∨)x,y∈G,满足不等式ρ(f(x·y),f(x)·f(y))<δ的映射f:G
4-差分置换是一类重要的密码函数,它在分组密码的非线性组件S-盒中有十分关键的应用,比如高级加密标准AES的S-盒使用的F28上的逆函数x-1(0-1=0)就是一个4-差分置换.在本文中,我
伽罗瓦内积是欧式内积和厄尔米特内积的推广,常循环码是一类结构丰富而又应用广泛的线性码,MDS码被著名学者MacWilliams和Sloane称为最富有魅力的纠错码,LCD码被广泛的应用于数
图像的边缘是图像最基本的特征之一,图像的大部分信息都集中在图像的边缘部分,边缘检测是图像分割,图像检索,区域目标提取等图像处理领域中十分重要的基础内容之一,边缘检测
本文讨论分析了两个生态系统的微分方程组模型,针对两种微生物竞争同一种营养物质,该论文建立微分方程模型。又考虑到生存环境中污染源毒素对微生物繁殖有作用,论文在方程组