正则2-连通图的最长圈 |
| |
引用本文: | 陈瑞袁.正则2-连通图的最长圈[J].福建师范大学学报(自然科学版),1983(2). |
| |
作者姓名: | 陈瑞袁 |
| |
作者单位: | 福建师大数学系 |
| |
摘 要: | P.Erdos和A M Hobbs在1]中提出如下的结论:设k≥6,G是2k个顶点的(k-2)次正则的2-连通图,则G是Hamilton图(以下简称为H图)。本文提出比上述结论更为广泛的定理:定理1 设k≥4,G是n个顶点的(k-2)次正则的2-连通图,则除G是peterson图外,G必有个长至少为min{n,2k}的圈。由于:(i)定理1中的k=4时,G是2-正则2-连通图,G是H图,它有个长为n≥min{n,2k}的圈;(ii)定理1中的k≥5且n≤3(k-2)时,根据2]中的B.Jackson定理知,这时G是H图,它有个长为n≥min{n,2k}的圈。因此,要证明定理1成立,只要证明如下的定理2成立。定理2 设n≥3k-5≥2k,G是n个顶点的(k-2)次正则的2-连通图,则除G是Peterson图外,G必有个长至少为2k的圈。在证明定理2的过程中,本文作下列的假设:
|
本文献已被 CNKI 等数据库收录! |
|