论文部分内容阅读
在一个图中,长为偶数的圈称为偶圈.令F表示图G的错误集.图G的一个点v为无错点,如果v(?)F.图G的一条边e=(u,v)为无错边,如果u,v(?)F且e(?)F.图G的一个圈C为无错圈,如果C既不包含错误点,又不包含错误边.令fv,fe分别表示F中错误点和错误边的个数.图G是边偶泛圈的,如果它的每条边都包含在一个长为l的偶圈中,这里l为介于4和顶点个数之间的任意偶数.图G是容错边偶泛圈的,如果G-F保持边偶泛圈性.本文主要研究二部图n-维超立方体Qn的容错边偶泛圈性.证明了在Qn(n≥3)中,如果fv+fe≤2n-5,fe≤n-2,且每个无错点均至少关联两条无错边,那么Qn的每条无错边都包含在一个长为l的无错偶圈中,其中l为介于6到2n-2fv之间的任意偶数Tsai在[Information Processing Letters,102(2007)242-246]中提出一个猜想：如果n≥4,fv+fe≤n-1,且每个无错点都至少关联两条无错边,则Qn的每条无错边均包含在一个长度为l的无错偶圈中,其中l为介于6到2n-2fv之间的任意偶数.结合Xu等人在[Information Processing Letters,96(2005)146-150]中的结果,我们证明了Tsai提出的这一猜想是成立的.