无爪图配对控制集问题上界的研究

来源 :华东师范大学 | 被引量 : 1次 | 上传用户:chenminer
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设图G=(V,E)是一个没有孤立点的无向简单图.如果V的一个子集S满足V\S中的每个顶点都有一个邻点在S中,则称S是图G的一个控制集.进一步,如果S是图G的一个控制集并且S导出的子图G[S]存在完美匹配,则称S是图G的一个配对控制集.一个图G的配对控制数,记为γpr(G),定义为min{|S|S是图G的一个配对控制集}.配对控制集问题就是确定给定图的配对控制数.该问题由Haynes和Slater于1998年在[1]中提出的,他们证明该问题对于一般图而言是NP-困难的.2009年,Goddard和Henning在[2]提出猜想:若G≠P(其中P是Petersen图)是一个n阶连通图且δ(G)≥3,则γpr(G)≤4n/7.本文将围绕该猜想对配对控制集问题进行研究,证明了对于m阶无爪连通图G,γpr(G)≤4n/7,并给出了达到上界的极值图.该结果证实了上面的猜想对n阶无爪连通图是成立的,同时改进了前人关于该问题上界的有关结果.
其他文献
扩散是生物个体之间相互远离的单线性运动,是生物的基本特征之一,对种群的分布、动态及遗传结构等方面均有重要影响。尤其是当种群内个体密度增加、食物及栖息资源不足的情况下,扩散对于这个物种的种群动态及种群发展都有着重要的意义。岩羊(Pseudois nayaur)被列为国家二级保护动物,属偶蹄目牛科羊亚科岩羊属,主要分布于青藏高原及其毗邻地区,是青藏高原特有种。研究区域选择在宁夏贺兰山自然保护区,贺兰山
我们首先证明了Miana和Romero提出的关于ballot数的如下猜想:对于m, n∈Z+,则有其中是第n个Catalan数.同时我们利用牛顿插值公式对其推广形式给出一个求和公式.例如我们证明了我们还给出了关于ballot数的和与交错和的模素数p同余式.例如:当p为大于3素数时,当p为大于5素数时,
文章给出了双参数量子除幂代数的定义,并将它实现为双参数量子A型包络代数的模代数,从而将单参数量子群的情形成功地推广到了双参数量子群的情形.利用“能级”这个概念,完成了双参数量子除幂代数的截头子模的每一个分次的模结构的研究,得出了每一个齐次子空间对应的子模都是单的或者不可分解的重要结论,其中当Socle为非单的情形时它是不可分解模,即子模中的任意一个元素都可以通过模作用交织提升至最高能级所对应的元素
本文研究一类半线性中立型时滞微分系统的逼近能控性.通过Laplace变换构造基本解并应用预解算子条件,Banach压缩映射原理和分数幂算子的相关技巧建立了这类系统逼近能控性的充分条件.所得的结果改进了这一领域已有的一些结论.最后用一个例子来说明所得结论的应用.全文分为5节:第1节简要介绍泛函微分方程及逼近能控性理论的相关背景知识和研究历程.第2节介绍关于解析半群和分数幂算子的预备知识.第3节构造基
本文主要研究的是相应于D型李代数的双参数量子群的凸性PBW型Lyndon基及其换位关系.首先利用生成元和关系式定义了Q(r,s)上的结合代数Ur,s(so2n).在此基础上,将,r和s限制为单位根,从而研究单位根处的D型双参数量子群,根据Lyndon树归纳地定义了相应于D型李代数根系的量子根向量,并且通过计算U+中量子根向量εi,j(1≤i≤j≤n-1),en,εi,j’(1≤i(≠n-1)
本文在基域F的特征为素数p(p≥3)的情况下,将除幂代数(?)((n,F))(p(?)n)实现为u(sl(n,F))-模,然后探讨(?)((n,F))的子模(?)(n;(?))的结构.因为(?)(n;(?))是其齐次空间(?)(n;(?))。构成的子模的直和,所以本文主要探究u(sl(n,F))-模(?)(n;(?))s的结构·文中首先利用(?)(n;(?))s中元素的能级将(?)(n;(?))s
杜杰、付强和王建磐在[20]中,定义了小q-Schur代数uq(n,r),并对其结构进行了研究,给出了各种形式的基.本文主要研究参量q是三次单位根时小q-Schur代数uq(2,r)的用生成元和关系式的实现,即它的表达(presentation)我们的方法对r的不同值进行分类讨论,先用生成元和关系式定义一个代数,然后证明这个代数和uq(2,r)同构.证明过程是利用已有的BLM基和坐标代数以及q-S
本文讨论了Leibniz代数F[x,y]的有限维商代数F[x,y]/In的导子代数和自同构.首先计算了n=1,2,3时商代数F[x,y]/In的导子代数,然后将其推广到一般n的情形.其次,确定了F[x,y]/I1的自同构以及F[x,y]/In(n≥2)的一些特殊自同构.
即便在看似简单的非线性问题中,解也可能会产生不同现象,例如边界层、内部层、角层,或者是多种情况的混合.本文主要研究了在如下一个含小参数的二阶非线性边值问题中,解对边值A和B的依赖关系,这里A和B不依赖于ε.由于该问题是非线性的,所以当边值发生变化时,解的定性性质将发生改变,即可能产生不同的现象.本文将参照Cole的意见,把A-B平面划分成九个区域.在对原方程进行Lienard变换,将其转换成等价的
设图G=(V,E是一个无向简单连通图,如果V的一个子集S使得V/S中的每个顶点都有一个邻点在S中,则称S是图G的一个控制集.进一步,如果S是图G的一个控制集并且由S导出的子图G[S]中有一个完美匹配,则称S是图G的一个配对控制集.一个图G的配对控制数,即图G的最小的配对控制集的大小,记为ypr(G). Chen, Sun和Xing [Acta Mathematica scientia Series