论文部分内容阅读
本文所给出的图在无说明的前提下,均为无向图。给定一个图G,V(G)和五(G)分别记作图G的点集和边集。连通的无圈图称为树,无圈图称为森林。Bn或者Tt,n-t是一个阶为n的完全二部图,其两部分分别记作(X,Y),其中|X|= t,|Y|= n- t。在同构的意义下,当n≥4和t≥1时, Bn或者Kt,n-t并不是唯一确定的。若图G和Bn为二部图,G的两个分部为V0和V1;Bn的两个分部为X0和X1。图G在二部图Bn中的嵌入记作σ,设σ是V(G)到V(Bn)的一个单射,使得σ(V0)?-X0,σ(V1)?-X1。图G1是图G的一个子图,如果存在树T在G的σi嵌入,其中1< i< k,i≠j且σ≠σi,则称树T为图G的一个k-填充。 Wang给出了一个猜想[7]:对于任意的n阶树T,和每一个整数k≥2,树T在完全二部图Bn+k=1中有k-填充。该猜想在k=2[5]和k=3[7]中得到了证明。本文证明该猜想在k=4时是正确的。即树T在完全二部图Bn+3中有4-填充,具体包括以下三个部分: 第一章介绍树在完全二部图中k-填充的一些基本概念,国内外的研究现状,本文所用的重要符号以及本文的主要研究成果。 第二章为了完成k=4的证明,本章给出了树T在完全二部图中有4-填充的几个重要的引理。 第三章我们主要证明了当k=4时,树T在完全二部图Bn+3中有4-填充。