论文摘要
设G=（V，E）为n个点的三连通图，令X（?）V（G）。C为G中的圈，如果对于G中任意的圈C′都有|X∩V（C）|≥|X∩V（C′）|，则称圈C为X-最长圈。我们用α（G）表示图G的独立数，α（X）表示G[X]的独立数。当k≤α（X）时σk（X）表示X中能组成独立集的k个点的度和（在G中）最小值；当k＞α（X）时令σk（X）=k（n-α（X））。设X（?）V（G），P为图G中的路，如果X（?）V（P），则称P为X-路。如果n为正整数且有n=∑i=1kni且ni≥2（1≤i≤k），其中ni（1≤i≤k）均为整数，则称（n1，n2，…，nk）为n的一个k-分解。在[4]中邹园提出如下结论：G为n个点的三连通图，C为G中的最长圈，R=G＼C，如果σ4（G）≥n+6，那么G[R]中任一连通分支H都满足|V（H）|≤2。我们可以对条件中的σ4（G）进行改动，即取V（G）的一个子集X，将σ4（G）改进为σ4（X），同时对结论作进一步的讨论得到本文的第一个结论：G为n个点的三连通图，X（?）V（G），C为一个X-最长圈，如果σ4（X）≥n+6，那么对于G＼C的任一连通分支H，有|V（H）∩X|≤2，而且恰含两个X中的点的连通分支不会含X外的点。易见此结论为[4]中邹园结论的推广。在[8]中Enomoto等人提出：G为n个点的连通图，如果有σ3（G）≥n或α（G）≤2，则G有哈密尔顿路或G中的最长圈均为强控制圈。我们对此结论的一部分进行改进，得到本文第二个结论：G为n个点的连通图，X（?）V（G），如果α（X）≤2，那么G有X-路。可见本文第二个结论推广了Enomoto的定理的部分结论。在[6]中陈耀俊等人给出结论：G为n个点的连通图，如果σ3（G）≥（3n-5）／2，那么G有哈密尔顿路。对其进行改进得到本文的第三个结论：G为n个点的连通图，X（?）V（G），如果σ3（X）≥（3n-5）／2，那么G有X-路。此结论为陈耀俊等人结论的推广。同样，在[7]中Robert Jahansson给出：G为n个点的连通图，给定n的一个k-分解（n1，n2…，nk）且ni（1≤i≤k）均为奇数，如果G有路P使得（?）v∈V（G）＼V（P）在P上都没有相继的邻点且dP（v）≥[n1／2]+[n2／2]+…+[nk／2]，那么G有点数分别为n1，n2，…，nk的点不交的路。改进此结论可得本文的第四个结论：G为n个点的连通图，X（?）V（G），|X|=s，（s1，s2，…，sk）为s的一个k-分解且si（1≤i≤k）均为奇数。设G有路P使得对任意x∈X＼V（P）都有|NP（x）∩X|≥[s1／2]+[s2／2]+…+[sk／2]且x在P上不会有相继邻点都在X中，那么G有点不交的路P1，P2，…，Pk使|Pi∩X|=si（i=1，2…，k）。易见Robert Jahansson的结论为本文的第四个结论的推论。在最后一章，我们提出了一些在今后研究中可以思考的问题。