论文部分内容阅读
设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阶树中具有最小离心距离和的树,并且得到了若干离心距离和的紧界.