无三角形的弱泛圈图

摘要

设G是n阶简单图,如果对于任意的整数l:3≤l≤n,G中含有长度为l的圈,则称G为泛圈图;如果G中含有长度在围长和周长之间的所有圈,则称G是弱泛圈图.关于泛圈图,Bondy(1971)证明了下面经典定理:每个边数至少为n<'2>/4的n阶Hamiltonian图是泛圈图或完全二部图.而后,Brandt(1997)改进了Bondy定理,证明了下面定理:每个边数至少为((n-1)<'2>/4)+1的n阶非二部图是弱泛圈图,并提出猜想:每个边数至少为[n<'2>/4]-n+5的n阶非二部图是弱泛圈图.随后,Bollobás和Thomason(1999)证明:每个边数至少为[n<'2>/4]-n+59的n阶图是弱泛圈图或二部图.在该文中,我们证明对无三角形的图,Brandt的猜想成立,即每个边数至少为[n<'2>/4]-n+5的n阶无三角形的非二部图是弱泛圈图.

目录

文摘

英文文摘

1.介绍

2.定理5证明的概述

3.极小反例的周长

4.含有(n-1)一圈的图

5.Hamiltonain图

6.定理5的证明

参考文献

致谢