论文部分内容阅读
Lovász和Plummer[28]在20世纪70年代提出猜想：每一个没有割边的3-正则图都有指数多个1-因子.本文讨论了一类广义Petersen图P(N，k)的1-因子数的下界及P(N，3)的Hamilton圈数的下界问题，证明了它们的下界均是指数级的.设k为奇数，当gcd(N，k)=1及gcd(N，k)≠1时，我们通过分别构造与广义Petersen图同构的新图并且仅考虑其中的一类情形就可以得到P(N，k)的1-因子数的下界是指数级的，这说明上述猜想对于这一类广义Petersen图P(N，k)是成立的.
其次根据Hamilton圈与P(N，3)的外圈的交-外圈路所构成的组合形式，找出了一类Hamilton圈对应于满足相应条件的自然数N的分拆，证明了P(N，3)的Hamilton圈数的下界亦是指数级的.