K_n-e图中的路因子

Path-factors in K_n-e graphs

G是一个Kn-e图,e∈E(Kn),设σ2(G)表示不相邻顶点度和的最小值.令|V(G)|=n=Σi=1kai,并且σ2(G)≥n+k-1.证明对于图G中任意的k个顶点v1,v2,…vk,存在点不相交的路P1,P2,…Pk,使得对于1≤i≤k,都有|V(Pi)|=ai,并且vi是Pi的一个端点.

G be a Kn-e graph, e ∈ E （Kn）, let σ2 （G） denote the minimum degree sum of a pair of nonadjacent vertices, Let ｜ V （ G ） ｜ =n=∑^ki=1ai, and suppose that σ2（ G ） ≥ n ＋k- 1 It is proved that for any k vertices v1, v2,… vk in G, there exist reflex disjoint paths P1 ,P2, …Pk such that ｜V（Pi） ｜=ai, and v, is a end-vertex of P, for 1 ≤i≤k .