控制数与拓扑指数的研究

发布时间：2020-08-19 20:04

【摘要】：设G =(V,E)是一个图,其中K = K(G)是图的点集,,E=E(G)是边集.G□H是图G和H的笛卡尔乘积.称D(?)V(G)是图G的一个控制集,若V(G)\D中每个点都与D中至少一点相邻.图G的最小控制集中点的个数称为控制数,记作γ(G).一个函数f:V(G)→ {0,1,2}是一个罗马控制函数(RDF),若每个赋值为0的点与至少一个赋值为2的点相邻.一个罗马函数f的权重定义为f(V(G))=∑u∈V G f(u).图G的罗马控制数γR(G)是图G所有罗马函数权重的最小值.设kk是一个正整数,称D D(?)V(G)是图G的一个距离kk-控制集,若不在D中的点都与D中至少一点的距离不超过k.图G最小距离kk-控制集中点的个数就是距离k-控制数,记为γk(G).拓扑指数是图论中不可忽视的研究内容,它是可以用来描述有机化合物的物理化学特性的数学参数.第一(M1)和第二(M2)Zagreb指数是源于共轭分子总π-电子能量研究的点度定义拓扑指数,定义为M1=∑u∈V(G)d2(u)和M2=∑uv∈E(G)d(u)d(v).离心距离和是利用点离心率定义的一个拓扑指数:ξd(G)=∑v∈V(G)-G(v)DG()其中点v在图G中的离心率εG(v)是指v到G中其它点的最大距离,且DG(v)是v到图G中其它点的距离之和.Harary指数是利用两点距离定义的一个拓扑指数:H(G)=1/2∑u∈V(G)∑v∈V(G)1/d(u.v),其中d(u,u)表示的是G中点u和v的距离.本文主要研究了关于控制数的Vizing猜想,以及(距离k-)控制数与上段中提到的拓扑指数之间的关系.第一章介绍了图论术语和符号以及本文研究内容的图论背景.Vizing猜想是由Vizing在1963年提出的关于控制数的一个著名猜想,即对任意图G和H都有γ(G□H)≥ γ(G)γ(H)成立.与Vizing猜想相关的不等式很少涉及罗马控制数,其中之一是由 Wu[Y.J.Wu,An improvement on Vizing's conjecture,Inform.Process.Lett.113(2013)87-88]得到的.本文第二章证明了 γR(G□H)≥γ(G)γ(H)+ 1/2min{γ(G),7(H)}在图G或者图H不是空图时成立.这一结果不仅改进了由Wu得到的结果,并且在某些条件下优于其他类似已有结果.AutoGraphiX(AGX)计算机系统是利用变邻域搜索方法和数据分析方法寻找图论猜想的一个软件.这些猜想主要确定图论中两变量的四则运算的界,同时刻画达到上下界的极值图.本文第三章我们改正了一个关于控制数和平均离心率的Auto-GraphiX猜想,并给出了修改后的猜想的证明.另外得到了 n阶树T的γ(T)-ecc(T)的紧上界.Borovicanin[B.Borovicanin,B.Furtula,On extremal Zagreb indices of trees with given domination number,Appl.Math.Comput.276(2016)208-218]确定了给定控制数的树的Zagreb指数的上界.在这一结果的启发下,本文第四章用距离kk-控制数给出了 n阶树的Zagreb指数的上界,并且刻画了相应的极值树.同时得到了一个用n,k,△表示的树的距离k-控制数的上界.最后利用已有的Harary指数与Zagreb指数的关系得到了给定距离kk-控制数的树的Harary指数的上界,并刻画了相应的极值图.本文第五章确定了给定距离k-控制数的n阶树中具有最小离心距离和的树,并且得到了若干离心距离和的紧界.
【学位授予单位】：安徽大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：

皇后,国际象棋,空格,笛卡尔乘积

，Ｇ和ｉ？■的笛卡尔乘积图（Ｃａｒｔｅｓｉａｎ邋ｐｒｏｄｕｃｔ邋ｇｒａｐｈ）邋Ｇ口丑丨ｕ邋ｅ邋Ｖ（Ｇ），邋Ｖ邋ｅ逦且两个点ｈｕ＇）与0；，？／）相邻邋逦或者ｕ＇邋＝邋？／且邋Ｖ（Ｇ）．对于文中出现的未定义的§１．２逦研究问题的背景逡逑所有研宄都围绕着控制数问题展开，与图论的起源类似，图戏：国际象棋游戏．国际象棋发源地在印度，图１．２．１呈现的际象棋的游戏规则，皇后可以在棋盘上横向，纵向，对角线上空格位置（假设这些方向上的空格上没有其他的棋子）？所以攻击（或者控制）标号为“ｘ”的空格位置．１９世纪５０年代，考虑如下一＂ｔ＂有趣的问题，棋盘上最少要放置多少个皇后可皇后占据，或被皇后攻击（或控制）？图１．２．１中放置的六个皇，随后被证实最少需要放五个皇后．这就是历史上著名的五个Ｘ逦１邋ＩＸ—

【相似文献】