不含K4和W4图的三角形填充和覆盖

作     者：杨亚珺 

作者单位：南京师范大学 

学位级别：硕士

导师姓名：许宝刚

授予年度：2020年

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：图 三角形填充 三角形边覆盖 K4 W4 

摘      要：设G=(V E)是简单图,取图G的一个三角形集合A,若A中的三角形是边不交的,即对任意的两个不同三角形Ti,Tj∈A,都有E[Ti]∩E[Tj]=(?),则称A是图G的一个三角形填充,在文章后面的证明中简称之为独立三角形集。图G的一个边子集E’(?)E(G),若与图G中的三角形均至少有一条边属于E’,即E[T]∩E’≠(?)对G的任一个三角形T均成立,则称E’是图G的一个三角形边覆盖,在文章后面的证明中简称之为横贯。定义v(G)=max{|A|:A为图G中的三角形填充},τ(G)=min{|E’|:E’为图G中的一个三角形边覆盖}.早在1984年,在文献[10]中,Tuza提出猜想:如果图G的任一个独立三角形集包含至多k个三角形,那么G有一个边数至多为2k的三角形边覆盖。换言之,猜想1:对于任意图G,均有不等式τ(G)≤2v(G)成立。对于某些特殊类型的图,得到了关于这一猜想的部分结果。在文献[11]中,Tuza证得对于平面图,无K5弦图,和具有n个顶点且至少7n/16条边的图,有不等式τ(G)≤2v(G)成立。在文献[9]中,Lakshmanan,Bujtas和Tuza证明了对于任意无奇轮的图,有不等式τ(G)≤2v(G)成立。1999年,在文献[4]中,由Haxell证得:对于任意图G均有τ(G)≤66/23v(G)。本篇学位论文主要关注任意无K4及W4的图G的填充和覆盖三角形问题。证明过程中先取固定图G的一个最大三角形填充B(最大的独立三角形集),取图G的三角形集合(B,1)(此三角形集合中的三角形均满足|E[T]∩E[B]|=1)。在(B,1)中再取一个独立三角形集合B1,相应的在B中存在一个与B1一一对应的独立三角形集合F,将B1与F相交的边集合记为{e(T):T∈B1}。接着可以证得G=E[B\F]∪ {e(T):T∈B1}是图G的一个三角形覆盖(横贯),从而得到τ(G)和v(G)的一个关系式τ(G)≤(3-2β)v(G)(1)接下来,在原图G中删掉边子集{e(T):T∈B1},得到图G的一个子图G’,再根据分析图G’中奇轮的三角形边的构成进行删边,从而使得图G’变成了一个无奇轮图。最后根据已知无奇轮图中成立τ(G)≤2v(G),结合在原图G中删掉的边,得到图G的另一个三角形覆盖(横贯),并且得到τ(G)和v(G)另一个关系式τ(G)≤(5/2+7/2β)v(G)+1/2(2)联立(1)和(2),得到τ(G)和v(G)的一个二元一次不等式组,化简后即可得对于任意无K4及W4的图G均有τ(G)≤31/11v(G)。