没有合适的资源?快使用搜索试试~ 我知道了~
255可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)171-183www.elsevier.com/locate/entcs关于三角剖分和小树宽图的TuzaF. Botler2巴西里约热内卢联邦大学计算机系统工程专业C.G. Fernandes3J. Guti'errez4DepartamentodeCipouchadaComputapouchaoUniversidadedeSaoPaulo,Brazil摘要Tuza(1981)证明了与每个三角形相交的最小边集的基数τ(G) 最多是G的边不相交三角形的最大集合的基数ν(G)的两倍。 在本文给出了关于图扎猜想的三个结果。我们对树宽的图进行了验证最多为6;证明了 对 每 个 平 面 三 角 剖 分 G ,τ(G)≤ 3 ν(G);τ(G)≤9ν(G)+1,如果G是树宽为3的极大图.关键词:三角形截线,三角形填充,树宽,三角剖分。1引言在本文中,我们使用术语图来指代简单图,而术语多重图来指代可能包含平行边的图。除此之外,符号和术语都是标准的。 图G的一个三角形横截是图G的一组边,去掉这些边后,图G成为一个无三角形图;图G的一个三角形填充是图G的一组边不相交的三角形。 我们记为τ(G)(resp. ν(G))1本研究部分由Coordenaperveeipervei perventodePessoaldeN′pervelSupreior资助。- 巴西(CAPES)-金融法001。C. G. 费尔南德斯得到了全国委员会的部分支持,Dese nvolvime ntoCie nt'enficcoe Tecnol'ogico-CNPq(Pr oc. 456792/2014-7、308116/2016-0和423833/2018-9)。J. Gut i'errezwassupportedbyFAPESP(Pr oc. 2015/08538-5)。2电子邮件:fbotler@cos.ufrj.br3电子邮件:cris@ime.usp.br4电子邮件:juanguti@ime.usp.brhttps://doi.org/10.1016/j.entcs.2019.08.0161571-0661/© 2019作者。出版社:Elsevier B.V.这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。172F. Botler等人/理论计算机科学电子笔记346(2019)171253 91最小三角形横截的基数(分别为最大三角形填充)。”[14]《明史》:“。猜想1.1(Tuza,1981)对任意图G,有τ(G)≤ 2 ν(G)。这一猜想在许多类图中得到了验证。 特别是图扎[15]Haxell和Kohayakawa [9]证明了若G是三部图,则τ(G)≤ 1. 956ν(G)。有关图扎猜想的更多结果,读者可参阅[1,5,6,8,10,11在本文中,我们提出了三个结果关于图扎猜想 我们对树宽不超过6的图进行了验证; 证明了对每个与K4不同的平面三角剖分G,τ(G)≤3ν(G),且若G是3-树,则τ(G)≤9ν(G 由K3得到的图,在图中依次选择一个三角形,并在相邻的三角形上添加一个新的顶点,三个顶点。Puleo[13]引入了一组处理包含小度顶点的图的工具(引理3.3),并验证了Tuza对于每个子图的平均度都小于7的图本文推广了Puleo的技巧(引理3.4),证明了树宽不超过6的图的请注意,有些图的树宽最多为6,最大平均度至少为7(图1)。图1. 树宽为6,平均度为22/ 3的图。在另一个方向,如[9]中所建议的,我们表明,对于某些类,图的比率τ(G)/ν(G)可以被一个小于2的常数所限制。具体地说,我们证明了,如果G是一个不同于K4的平面三角剖分,那么τ(G)≤ν(G)(定理4.5),若G是3-树,则τ(G)≤ν(G)+(Theo-2 5 5rem5.2)。本文的组织结构如下。在第2节中,我们建立了符号,并提出了一些辅助结果,在整个文件中使用。在第三节中,我们验证了图扎最后,在第6节中,我们提出了一些结论性意见。由于篇幅所限,我们只给出一些证明的草图。2有根树分解在这一节中,我们将介绍有关树分解的大部分符号和一些辅助结果根树是一个对(T,r),其中T是一棵树,r是一个F. Botler等人/理论计算机科学电子笔记346(2019)171173∈结T.给定t V(T),如果tJ是T中连接r的(唯一)路径中的节点和t,那么我们说tJ是t的祖先。T中的每一个以t为祖先的顶点称为t的后代。 如果ti=r,则t的父代,记为p(t),是t的邻近于t的祖先。t的后继节点是父代是t,我们用ST(t)表示t没有后继节点的T节点是T的叶子节点。t的高度,用hT(t)表示,是连接t和t的后代的最长路径的边数。当T从上下文中清楚时,我们简单地写S(t)和h(t)。定义2.1图G的树分解是由树T和集合V={Vt<$ V(G):t∈V(T)}组成的对D=(T,V),满足以下条件:(i){Vt:t∈V(T)}=V(G);(ii) 对任意uv∈E(G),存在t∈V(T)使得u,v∈Vt;(iii) 如果一个顶点v在Vt1<$Vt2中,则对于T的连接路径中的每个t,v∈Vtt1和t2。D的宽度是数字max {|V t| − 1:t∈V(T)},而G的树宽tw(G)是G的最小宽度的树分解的宽度。设G是树宽为k的图。如果|V t|对于每个t∈V(T),= k + 1,并且|V tV t′|= k对于设(T,V)∈E(T),则称(T,V)是G的满树分解.Bodlaender [2]证明了下面的结果(也见Gross [7])。命题2.2每一个图都有一个完全树分解。一个三元组(V,T,r)是图G的一个根树分解,如果(V,T)是图G的一个满树分解,(T ,r)是一个根树,且Vt<$Vp(t)=/对于任意t∈V(T)\ {r}和TJ∈S(t),Vt <$Vt ′.每一个满树分解都可以被修改为一个根为r的有根树分解。所以下面的命题就来了自然.命题2.3每个图都有一个有根树分解。给定图G的一个根树分解(V,T,r)和一个节点t∈V(T)\{r},我们说Vt\Vp(t)中的(唯一)顶点是t的代表。我们离开代表团成员R。我们用NG(u)表示顶点u∈V(G)的邻点集.当G从上下文中清楚时,我们简单地写为N(u)。在下文中,我们用N[u]表示u的闭邻域N(u)<${u},用d(u)表示u的度,用Δ(G)表示G的最大度。注2.4若y是图G的根树分解的叶t的表示,则NG(y)≠Vt.174F. Botler等人/理论计算机科学电子笔记346(2019)1713树宽不超过6的图在本节中,我们通过扩展Puleo [ 13 ]引入的技术来验证树宽不超过6的图的Tuza为此,我们使用以下定义(参见[13])。定义3.1对于一个图G,一个非空集合V0<$V(G)称为可约的,如果在G中存在一个集合X<$E(G)和一个由边不相交的三角形组成的集合Y,使得下列条件成立:(i) |X| ≤ 2 |Y|;(ii) X<$E(A)/=X,对于G中每个包含V0的顶点的三角形A;并且(iii) 如果u,v∈/V0且uv∈E(A),对于某个A∈Y,则uv∈X。在这种情况下,我们说(V0,X,Y)是G的一个约化三元组.如果G没有可约集,则称G为不可约集。下面的引理是自然的(见[13,引理2.2])。引理3.2设(V0,X,Y)是图G的一个约化三元组,并设GJ=(G-X)−V0。 若τ(GJ)≤ 2 ν(GJ),则τ(G)≤ 2 ν(G).我们说一个图G是鲁棒的,如果对任意v∈V(G),G[N(v)]的每个分支的阶数至少为5。我们经常使用下面的结果(见[13,引理2.7])。引理3.3设G是不可约鲁棒图,x,y∈V(G).以下陈述成立:(a) 如果d(x)≤ 6,则Δ(G [N(x)])≤ 1,|E(G [N(x)])|/= 2;(b) 若d(x)≤6且d(y)≤6,则xy∈/E(G);(c) 如果d(x)= 7且d(y)= 6,则N[y]/N [x];以及(d) 若d(x)≤8且d(y)= 5,则N[y]/<$N [x]。我们在下面的引理中推广了上面的结果。引理3.4设G是不可约鲁棒图,x,y∈V(G). 如果d(x),d(y)≤ 6,|N(x)<$N(y)|≤ 7,则(i)d(x)= d(y)= 5;(ii)|N(x)<$N(y)|= 3;和(iii)G [N(x)] G [N(y)] K5.证明证明由一系列案例的分析组成。在每一种情况下,我们都找到了G的一个约化三元组,这与G的不可约性相矛盾。在这个扩展的摘要中,我们只给出(i)的证明利用引理3.3(b),我们证明了xy∈/E(G). 假设,在不损失一般性y的情况下,d(x)≥d(y)。 因为G是鲁棒的,所以d(y)≥5。 对于矛盾,设d(x)=6,令N(x)={v1,v2,v3,v4,v5,v6}。在下文中,我们分析其中d(x)=d(y)=6的情况;其中d(x)= 6且d(y)= 5的情况为:相似F. Botler等人/理论计算机科学电子笔记346(2019)171175Xyv3v6(一)v2v1(b)第(1)款v1v7(c)v1v7(d)v1v7v4v5xv2v3v6yxv2V5V3v4v6yxv2V5V3v4v6yv5v4图2.引理3.4的证明。Y中包含x和y的三角形分别用蓝色和绿色表示,而Y中既不包含x也不包含y的三角形则用红色表示。虚线边缘示出可能不存在的边缘因为|N(x)<$N(y)|≤ 7时,我们可以假定N(y)<${v2,v3,v4,v5,v6}。通过引理3.3(a),不失一般性,我们可以假设E(G[N(x)]){v1v4,v2v5,v3v6}。案例1. N(y)= N(x)。让X=E(G[{v1,v2,v3,v4,v5,v6}])和Y={v1v3v5,v2v4v6,xv1v2,yv2v3,xv3v4,yv4v5,xv5v6,yv1v6}。然后|X| ≤ 15 ≤ 16= 2 |Y|而({x,y},X,Y)是G的约化三元组(图2(a)),这是一个矛盾。案例2. N(y)/=N(x)。则N(y)={v2,v3,v4,v5,v6,v7},其中v7∈V(G)\{v1}.通过引理3.3(a),不失一般性,我们可以假设E(G[N(y)])<${v2v5,v3v6,v4v7}。设H=G[{v2,v3,v4,v5,v6}].我们有三个案子。分案2.1. |=0。|= 0.设X={xv1,yv7}∈E(H)且Y={v2v4v6,v3v4v5,xv2v3,xv5v6,yv2v5,yv3v6}。因此|= 2 +|E(H)|=12 = 2 |Y|并且({ x,y },X,Y)是G的一个约化三元组|and ({x,y}, X,Y) is a reducing triple for G(图2(b))矛盾。分案2.2. |=1。|= 1.没有损失的一般性,我们可以假设的v2v5∈E(H)。设X={xv1,yv7,v3v7} ∈E(H),Y={v2v4v6,v3v4v5,xv2v3,xv5v6,yv2v5,yv3v7}.因此|X|= 3+ |E(H)|= 12 = 2 |Y|并且({x,y},X,Y)是G 的 一个 约化三元组(图2(c)),矛盾。分案2.3. E(H)={v2v5,v3v6}。设X={xv1,yv7} ∈E(H),Y={v2v4v6,xv2v3,yv3v4,xv4v5,yv5v6}.所以|= 2 +| E(H)|=10 = 2 |Y|而({ x,y },X,Y)是G的一个约化三元组(图|and({x, y}, X,Y ) is a reducing triple for G (Fig- (2)(D)(A)(D)(A)(B)(C)(D)(A)(D)(A)(D)(D)(Q利用引理3.3和3.4,我们证明了树宽不超过6的图的Tuza176F. Botler等人/理论计算机科学电子笔记346(2019)171定理3.5若G是树宽不超过6的图,则τ(G)≤ 2 ν(G).证明假设,对于一个矛盾,该陈述不成立,设G是树宽至多为6且τ(G)> 2 ν(G)的图,|V(G)|.我们称G是不可约的。事实上,假设G有一个约化三元组(V0,X,Y),设GJ=(G-X)-V0。注意GJ的树宽至多为6,且τ(GJ)≤2ν(GJ)是由G的极小性决定的.由引理3.2,τ(G)≤2ν(G),一个矛盾.可以通过导出与G的极小性的矛盾来检查G是鲁棒的,如果存在F. Botler等人/理论计算机科学电子笔记346(2019)171177一个顶点v,其中G[N(v)]包含一个至多有四个顶点的分量所以G是不可约的和鲁棒的。假设|V(G)|≤ 7。则由引理3.3(b)证明Δ(G)≤6,且E(G)=0.因此τ(G)≤2ν(G)是一个矛盾。 因此|V(G)|≥ 8。 根据命题2.3,G有一个根树分解(T,V,r)。因为|V(G)|≥ 8,我们有|V(T)|> 1,因此有一个节点t ∈ V(T),h(t)= 1。如果t=r,设vt是t的代表;否则,设vt是Vt的任意顶点。首先,假设S(t)={tJ},设x是tJ的代表。 我们有d(x)∈ {5,6}由注2.4和因为G是鲁棒的。 重新标记2.4应用于G−x和t意味着N G−x(v t)<$V t,因此d(vt)=|N(vt)| ≤|NG−x(vt)|+ 1≤|Vt| ≤7。若d(vt)=7,则vtmu与x相邻,且V t\ {v t}中的每个顶点都相邻.因为V t′ <$V t<${x},我们有N [x]<$N [vt],这与引理3.3(c)或引理3.3(d)矛盾。所以d(vt)≤6,且y引理3.3(b),vtx∈/E(G). T husN(x)<$N(vt)<$Vt\{vt},因此|N(x)<$N(v t)|≤ |Vt| − 1 ≤ 6。 另一方面,引理3.4意味着d(x)= d(v t)= 5,|N(x)<$N(vt)|= 3,这意味着|N(x)<$N(v t)|= 7,a矛盾因此|S (t)|>1.现在假设的|≥3,|≥ 3,和让t1,t2,t3∈S(t).设z i是t i的代表,=一二三通过重新-标记2.4,|N(z i)<$N(zj)|≤ |V t| = 7,对于i,j∈ {1,2,3}且i/= j。因此,通过引理3.4,d(z i)=5,并且对于每个i ∈ { 1,2,3 },G [N(z i)] K5,并且|N(z i)<$N(zj)|=3,对于i,j∈{1,2,3}且i=j。 LetN(z1)={v1,v2,v3,v4,v5}.因为|N(z1)<$N(z2)|= 3,我们可以假设,不失一般性,N(z2)={v3,v4,v5,v6,v7}。 不难检查N(z3)在N(z1)<$N(z2)中是否只包含一个顶点,因为|N(z1)<$N(z3)|为|N(z2)<$N(z3)|= 3和|N(z3)|= 5。因此,我们可以假设,不失一般性,N(z3)={v1,v2,v3,v6,v7}。设H=G[{v1,v2,v3,v4,v5,v6,v7}],并注意H的每对顶点至少包含在一个N(zi)中,其中i∈{1, 2, 3}.因此,由于G[N(zi)]K5对于i∈{1, 2, 3},我们有HK7。 设X = E(H),注意:|X| = 21。放和Y1={z1v1v4,z1v2v5,z2v3v4,z2v5v6,z3v1v6,z3v2v3}Y2={v1v2v7,v2v4v6,v3v6v7,v4v5v7,v1v3v5},Y=Y1<$Y2。注意|Y| = 11,因此|X| ≤ 2 |Y|,因此({z1,z2,z3},X,Y)是G的一个约化三元组(图3),这是一个矛盾。我们的结论是|S(t)|= 2。设t1,t2∈S(t),x,y分别为t1,t2同样,d(x)= d(y)= 5,|N(x)<$N(y)|= 3,并且G [N(x)],G [N(y)] K5,通过注释2.4和引理3.4。因此,Vt<$N(x)<$N(y)。注意,t是(TJ,VJ,r)的叶,其中TJ=T−t1−t2且VJ=V\{Vt1,Vt2}。因此dG−x−y(vt)≤6byRe-mark2.4,且dG(vt)≤8。注意vt∈N(x)<$N(y)。不失一般性,假设vt∈N(x)。当G[N(x)]是完全图时,N[x]<$N[vt]是引理3.3(d)的反证. 证明到此结束Q由于K8-free弦图的树宽最多为6,定理3.5一般-178F. Botler等人/理论计算机科学电子笔记346(2019)171推广了Tuza关于弦图的一个结果[15,命题3]。推论3.6若G是K8-free弦图,则τ(G)≤ 2 ν(G).4平面三角剖分本节中所有新的定义都取自邦迪和默蒂的书[3,第10章]。一个图是平面的,如果它可以画在平面上,使其边缘相交,只有在他们的端点。我们把这种平面图称为平面图。平面图将平面划分为弧连通的开集,我们称之为面。平面图中的面f的边界是通常拓扑意义下的开集f的边界。如果两个面的边界有一条公共边,则这两个面是相邻的。给定平面图G的对偶图G是其顶点集是G的面集的多重图,且其中两个顶点由k条边连接,如果对应面的边界有k条公共边。注意,如果G有一个桥,那么G包含一个环。因此,简单平面图的对偶图没有桥。一个简单的连通平面图,其中所有的面都有三条边,称为平面三角剖分。平面三角剖分是一个允许平面三角剖分的图。简单连通平面图是三角剖分图当且仅当它的对偶图是无桥三次重图。此外,三角剖分的对偶只有在三角剖分是单个三角形时才有平行边。此外,每个平面三角剖分都有一个唯一的平面三角剖分,因此我们将引用它的面和它的对偶。平面图中的面三角形是作为其一个面的边界的在这一节中,我们证明了对每个不同于K4的平面三角剖分G,τ(G)/ν(G)≤3/ 2.如果G=K5−e,则τ(G)/ν(G)= 3/ 2。因此,这个界限是紧的。如果G是三角形,则τ(G)=ν(G)= 1。所以我们可能假设G不是K3。证明分为两部分。在引理4.2中,我们给出了τ(G)的一个上界,在引理4.4中,我们给出了ν(G)的一个下界。对于引理4.2的证明,我们需要以下Petersen定理(见[12])。定理4.1(Petersen,1981)每个无桥三次图都包含一个完美匹配。引理4.2如果G是平面图,则τ(G)≤n− 2。z1v3v4v2v5v1z2v6v7z3图3.定理3.5的证明。Y1中包含z1、z2和z3的三角形分别用蓝色(点线)、绿色(虚线)和青色(点划线)表示,而Y2中包含z1、以红色(实线)表示。F. Botler等人/理论计算机科学电子笔记346(2019)171179−∗3333ν(G)3我们可以假设n≥4。 设H是包含G的极大平面图并且注意τ(G)≤τ(H)。 根据欧拉 因为H是平面三角剖分图,所以H是2n4顶点的无桥三次图因此,在本发明中,根据定理4.1,H_∞包含完美匹配M_∞。设M是H的与M中的边对应的边。注意|M|为|M|= n− 2。因为H−M只包含偶数度的顶点,所以H−M是一个二部图。因此H−M没有三角形,因此τ(H)≤|M|= n − 2。Q为了证明ν(G)的下界,我们使用著名的Brook定理 (see[4])。图G的色数记为χ(G).定理4.3(Brooks,1941)若G是连通图,则χ(G)≤Δ(G)或G要么是奇圈,要么是完全图.引理4.4若G是与K4不同的平面三角剖分,则ν(G)≥2(n−2)。证明我们可以假设G K3.G的对偶G是一个三次图,从K4 由定理4.3可知,存在G的独立集Y∈,至少|V(G)|顶点。 设Y是G的面三角形,对应于Y中的顶点。 由于Y是G中的一个独立集,所以Y是G中的一个三角形填充。因此v(G)≥|为|Y|≥| V(G)|=2(n − 2)。|= 2 (n − 2).Q本节的主要结果直接来自引理4.2和4.4。定理4.5若G是与K4不同的平面三角剖分图,则τ(G)≤2我们还能够得到下面的引理4.4的稍微强一点的版本,用于一类(有限)平面3-树。这个结果将在下一节中使用。给定平面3-树G中K4的一个拷贝H,我们用g(H)表示对(i,j),其中 i(分别为j)是最大值(相应地,最小)的顶点数G内的一个面H。我们说一个平面3-树G是限制的,如果G包含K4的一个拷贝H,使得g(H)=(2, 0).在这种情况下,我们总是把H的没有G的顶点在内的面看作G的外面,即G不在H中的顶点画在H的内面上。另外,如果H有两个面,其中恰好有G的一个顶点,那么我们说G是超限制的。命题4.6如果G是一个限制的(相应地,超限制的)平面3-树,则存在G的包含外部面的面三角形的三角形packingP,并且使得|P| ≥[f/3|(分别)|= 5)。|=5).证明设v是G的顶点,对应于G的外表面,并且设GJ=G−N[v]。 由于G是一个三次图,GJK4。 根据定理4.3,GJ包含一个独立集合IJ,其中[(f −4)/3|顶点,因此对应于IJ{v}中顶点的G的面三角形的集合P是包含外部面的G的面三角形的三角形填充,并且使得|P| ≥ [(f− 4)/3 |+1。因此,如果f− 1/f − 0(mod 3),则[(f− 4)/3 |+ 1 =[f/3 |P是所需的三角形填充。因此,我们可以假设f−1< $0(mod 3),因为G是限制,G是图4中的前十个图之一,它们有10个面,180F. Botler等人/理论计算机科学电子笔记346(2019)171Δ55ΔJ 联系我们916915555555555555555和至少4个独立面(包括外表面),或16个面和至少6个独立面(包括外表面)。如果G是超限制的,则G是图4中最后两个图之一。Q图4. 所有10棵具有f≠1(mod 3)面的限制平面3-树和两棵超限制平面3-树。在完整版的文件中,我们证明命题4.6不能扩展到一般的平面3-树。53-树在这一节中,我们证明了对任意3-树G,τ(G)≤9ν(G)+1.给定一个图G,一个横截X和一个三角形填充Y,我们称对(X,Y)是一个9-TP G如果|X| ≤9|Y|+1。注意,如果G有9-TP,则τ(G)≤9ν(G)+1.设(T,V,r)是图的根树分解G. 给定节点t∈V(T)\{r},我们用R(t)表示所有代表的集合所有T的后代。注意,t的代表也在R(t)中。 再称S(t)是t的后继集. 对于每一个三重顶点ΔV t,设SΔ(t)={TJ∈S(t):Vt ′ <$Vt= Δ}.当t从上下文中很清楚时,我们简单地写S。我们的证明依赖于对高度较小的节点的分析,这保证了最小反例具有特定的配置。对于高度为1的节点,我们给出以下引理。引理5.1设G是一棵3-树,使得τ(G)>9ν(G)+1,且G是上最小5 5所有这些图表。 设(T,V,r)是G 的 一个宽度为3的根树分解,设t ∈ V(T)\ {r}. 如果h(t)= 1,则|S(t)|= 1。证明设V t={a,b,c,d}.为了解决矛盾,假设|S(t)|> 1.在不失一般性的情况下,假设V t =Vp(t)={b,c,d}。 令S(t)={t1,t2,.,t k}。对于每个i∈[k],设vi是ti的代表。因为h(t)= 1,所以Δin{abc,abd,acd}中的至少一个使得SΔi=1。假设恰好有一个三角形Δ在abc,abd,acd,say Δ =abc,使得S= . 设G=GR(t). 注意GJ是一棵3-树。利用G的极小性,存在GJ的一个9-TP,即(XJ,YJ).因此,(XJ<${ab,bc,ac},Y J<${acv1,abv2})是G的9-TP,矛盾。在-事实上,τ(G)≤τ(GJ)+ 3≤9ν(GJ)+16≤(ν(G)−2)+ ≤ ν(G)+(图-(第5(a)段)。 因此,我们可以假设在{abc,abd,acd}中至多有一个三角形Δ是因此,SΔ=π。那就这样吧|S(t)|=2的条件下,在一般情况下,证明了t1∈Sabc,t2∈Sabd.设GJ= G −R(t)。同样,GJ是一棵3-树。通过G的极小性,存在GJ的一个9-TP,即(XJ,YJ). 设e ∈ XJ<$E(bcd). 在不失一般性的情况下,我们有两种情况。 如果e = bc,则令X = XJ<${ad,av1,bv2}。如果e = cd,则令X =XJ<${ab,cv1,dv2}。 在这两种情况下,(X,Y J<${acv1,abv2})是G 的9-TP,矛盾(图5(b))。最后假设,|S(t)|≥ 3。F. Botler等人/理论计算机科学电子笔记346(2019)171181(b)第(1)款一C一5555不 失 一 般 性 , 假 设 t1∈Sabc 且 t2 、 t3∈Sabd , 或 者 t1∈Sabc 、 t2∈Sabd 且 t3∈Sacd 。 设GJ=G−R(t)。通过G的极小i y,x是G j的一个9-TP,say(XJ, YJ).注意E( bcd ) <$X J/=<$。因 此 ( XJ∈ {ab , bc , cd , ac , bd , ad} , YJ∈ {acv1 ,abv2adv3})是G的一个9-TP,一个矛盾(图5(c)). 证明到此结束Qb b b(c)第(1)款d dcd图5.引理5.1 的证明。在下面,我们证明本节的主要定理。定理5.2若G是3-树,则τ(G)≤9ν(G)+1.证明假设,对于一个矛盾,陈述不成立。设G是τ(G)>9ν(G)+1的所有3-树上的极小反例.我们声称5 5如果(T,V,r)是G的一个宽度为3的根树分解,则|V(T)|≥ 4。的确如果|V(T)|= 1,则|V(G)|= 4,τ(G)= 2,且ν(G)= 1。如果|V(T)|= 2,则|V(G)|= 5,τ(G)= 3,且ν(G)= 2。 如果|V(T)|= 3,则|V(G)|= 6,τ(G)≤4,且ν(G)= 3。在每种情况下,我们都反驳τ(G)>9ν(G)+1。由于5 5由于篇幅所限,我们省略了下一个主张的证明5.3存在G的一个宽度为3的有根树分解(T,V,r),其中节点t∈V(T)\ {r}使得h(t)= 2。设(T,V,r)是由权利要求5.3给出的G的根树分解,并且设t是T中的节点,其中h(t)= 2。令L ={11,...,l m}是t的后继集即叶子,并且令Q = S(t)\L={q1,.,q k}。对于每一个i∈ [m],设u i是li的表示. 根据引理5.1,|S(qi)|i∈[k]=1。对于每一个例子,令S(qi)={qiJ},并且vii是qi的表示,viJ是qiJ的表示(图6)。 令QJ={q1J, . ,qkJ}。LetVt={a,b,c,d},并且在不失一般性的情况下,假设Vt=Vp(t)={b,c,d}。不l1l 2···lmq1q2···qk(u1)(u2)(um)(v1)q1J(v1J)(v2)Q2J(v2J)···(vk)qkJ(vkJ)图6.以t为根的子树。5.4设Δ是Vt中的一个顶点三元组,其中 Δ以及(ii)SΔ(t)<$L=<$L或SΔ(t)<$Q=<$Q。bcd。(i)|SΔ(t)|≤2;(一)一C182F. Botler等人/理论计算机科学电子笔记346(2019)1715555Δ∈5由于篇幅限制,我们省略了(i)的证明对于(ii),假设,对于aΔcontradiction,Δ=abd,l1,q1∈S(t). SayVq1<$Vq1′ ={x0,x1,v1},设GJ=G−v1J。 若G是极小的,则存在G j的一个 9-T P,say(XJ, YJ). 不失一般性 , 假 设 yyJ∈ XJ<$E ( x0x1v1 ) , 令 z∈ {x0 , x1 , v1}\{y , yJ} , 且 令X=X J<${zv1J}。注意X是G的一个transv。SuposewwJ∈E(x0x1v1)\E(YJ).因此,(X,YJ<${wwJv1J})是G的一个9-TP,一个连续的矛盾。 因此,x0x1v1的 每条 边 都在E(YJ)中. 由于dG′(v1)= 3,我们必须有x0x1v1∈设x2v1∈/E(YJ). 另一种情况是x0u1和x1u1不在E(YJ)中.则(X,YJ\{x0x1v1} <${x0v1v1J,x0x1u1})是G的一个9-TP,一个连续矛盾. 所以在x0u1和x1u1之间至少有一个,比如x0u1,在E(YJ)中由于dG′(u1)= 3,x0x1v1∈YJ,我们有一个x0x2u1∈Yj,且x1u1∈/E(YJ). 但随后(X,YJ\{x0x1v1,x0x2u1}{x1v1v1J,x0x2v1,x0x1u1})是G的一个9-TP,是一个约束.Q我们继续进行定理的证明.滥用符号,对于每个顶点的三元组Δ<$Vt,如果SΔ(t)=<$,则Δf=bcd,leth(Δ)=0 ,否则h(Δ)= 1 + max{h( TJ): TJ∈SΔ(t)}。 设kJ=|{Δ V t:h(Δ)= 2}|、mJ=|{Δ V t:h(Δ)= 1}|.设G ~+是由G [Vt <$R(t)]通过变换得到的图,对于每个顶点的三重数Δ<$Vt,满足Δt=bcd,|SΔ(t)|=2,R(x)中的顶点,对于恰好一个xS(t)。 可以通过权利要求5.4来检验,G+是一个受限的平面3-树。此外,G+有f= 4+ 4kJ+ 2mJ面。设Q+是集合{qi∈Q:vi∈/V(G+)}. 由图4.6可知,G+包含一个三角形,该三角形填充了包含面bcd的面三角形的P +,并且使得|P+|≥ [f/3|,如果G+是超受限的,那么|P+|=5。 对于qi∈Q+,tTi=viviJwi,其中wi是vi和viJ之间的顶点,tP=P+n{Ti:qi∈Q+}. 注意|P|为|P+|+(k-k J)。5.5设GJ= G−R(t).若XJ是G j的断面,则(i)存在G的断面,|XJ| +1 +2 k + m;(ii)存在G的一个横截,其大小至多为|XJ| +5 + k。证明(i)由于XJ是GJ的断面,bcd是GJ中的三角形,X JE(bcd).在不损失一般性y的情况下,假设bc∈X J。Given一 4-团 钾 G和 一 设置 XE(G) 等 的 E(K)<$X={e},记为通过K<$X,K中唯一不与e共享任何顶点的边。 例如,Vt{bc}=ad。对于每个i∈[m],设ei=Vli <${bc,ad}。对任意i∈[k],设fi=Vqi<${bc,ad},fiJ=Vqi′<${bc,ad,fi}.注:X=XJ<${ad}<${ei:i∈[m]}<${fi:i∈[k]}<${fiJ:i∈[k]}是G的一个断面,|为|X J |+1 +2 k + m。|+1+ 2 k + m. (ii)设X=XJ<$E(G[Vt])<${vi viJ :i∈[k]}。注意X是G的横截。因为XJ是GJ的横截,bcd是G j中的三角形,X J<$E(bcd)<$,因此|X JE(G[Vt])|≥1。我们|为|X J|+的|E(G [ V t ])|−| X j E(G [ V t ])|+k ≤ |XJ|+5+ k。|+5+ k.Q设GJ=G−R(t),(XJ,YJ)是GJ的一个9-TP。P中唯一包含GJ的边的三角形是bcd。因此Y = Yj(P \ {bcd})是G的一个三角形填充,|YJ|+的|P+| − 1 +(k-kJ)。 根据权利要求5.5,存在G的横截X,|XJ| + min {1 + 2 k + m,5 + k}。 注意kJ≥1,因为h(t)= 2。F. Botler等人/理论计算机科学电子笔记346(2019)171183555555≤ 5|≤ 5|+.555≤5|+(k+2)5 5kJ+mJ≤ 3。如果mJ= 2,则kJ= 1,G+是超限制的。在这种情况下,因为5(5+ k)<9(3 + k),我们有,|X| ≤ |XJ|2019- 05 - 25 01:05:<05(|Y J|+3+ k)+1=10月20日,|YJ|+的|P+| − 1 +(k-kJ))+1≤9|Y|+1。 所以我们可以假设mJ≤1。注意,对于kJ和mJ的所有可能值,我们有[f/3 |− 1 +(k-kJ)=[(4+4kJ+2mJ)/3|−1+k−kJ=1+k+[(kJ−2+2mJ)/3|=1+k+[kJ/3]+[mJ/2|. 假设k≤2。则我们有10 k≤ 9 k + 2和5 m≤ 9 [m]/2 |+ 2,因为mJ≤m≤ 2 mJ≤ 2,因此5(1 + 2 k +m)= 5 + 10 k + 5 m≤ 5+ 9 k +2+9 [m]/2 |+2 = 9(1 + k +[m]/2|)的。而且我们|≤ | XJ|+1 +2 k + m Y J|+ +。|+ +.1 +k+,|919mj91552现在假设kJ≤2且mJ= 0。 由于kJ≥ [k/2|,我们有k≤ 4,因此10 k≤ 9 k + 4。此外,我们有m = 0 =[mJ/2|因此,5(1 + 2 k + m)= 5 + 10 k + 5 m≤ 5 + 9 k + 4 +9 [m]/2 |= 9(1 + k +[m]/2|)的。类似于上面的情况,我们有|X| ≤ |XJ| +1 +2 k+ m≤9|Y|+1。因此,我们可以假设k≥3,并且kJ= 3或mJ= 0。 这意味着5k = 9k− 4k≤ 9k− 12,因 此 5 ( 5 +k ) = 25 + 5k≤ 9k + 13≤ 9 ( k+ 2 ) 。 此 外 , 我 们 还 得 到[kJ/3]+[mJ/2| ≥1。所以,完全的保护是因为9 1 9|≤ |X J|+5+ k YJ|+的 |+≤9。|+1+k +,kj,+,m j,n+ 1=9|Y|+1。|+1.5 325 5 5Q6总结发言本文给出了与图扎猜想有关的三个结果。在第3节中,我们得到了一个引理(引理3.4),它扩展了Puleo由于图扎猜想的任何最小反例都在第4节和第5节中,我们得到了图扎猜想对于特定图类的更强版本我们相信,这里使用的技术也可能是有用的,以处理其他类别的图,也许通过引入新的成分。引用[1] J. D.巴伦和J·卡恩。图扎猜想对稠密图是渐近紧的。组合可能吧Comput. ,25(5):645[2] H. L.博德兰德树宽有界的图的部分k-树园。理论计算。Sci. ,209(1-2):1[3] J. A.邦迪和U。S. R. Murty. 图论,数学研究生课本第244卷。Springer,New York,2008.[4] R. L.布鲁克斯关于网络节点的着色。剑桥哲学会数学学报,37(2):194-197,1941.184F. Botler等人/理论计算机科学电子笔记346(2019)171[5] X. Chen,Z. Diao,X. Hu和Z.唐图扎关于填充和覆盖三角形猜想的充分条件在组合算法,第9843卷的讲义在计算。Sci. 第266-277页。Springer,2016.[6] Q. Cui,P. Haxell,and W. MA.平面图中的填充与覆盖三角形。图表和组合。,25(6):817[7] J. L.恶心固定树宽和有界度的图的嵌入。Ars Math. Contemp. ,7(2):379[8] P. E. 哈塞尔图中三角形的填充和覆盖 离散数学,195(1):251[9] P. E. Haxell和Y.早川三部图中的填充与覆盖三角形。图表和组合。,14(1):1[10] P. E. Haxell,A. Kost och ka和S. 托马斯是的。无K_4平面图中的可折叠三角形.图表和组合。,28(5):653[11] M.克里维列维奇关于图扎关于三角形的填充和覆盖的一个猜想。离散数学,142(1[12] J. 佩特森。 DieTheoriederreguléarenGraphs. 一个cta数学。,15(1):193-220,1891.[13] G. J. Puleo。最大平均度小于7的图的
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功