图的有特殊性质的k-因子和半-k-因子

k-Factors Wk-Factors and Semi-k-Factors With Special Properties in Graphs

设 k≥ 1是一个整数 ,G是一个 2 -边连通图 ,U是 V( G)的子集 .设 F是 G的支撑子图 ,使得对所有 x∈ V( G) - U,有 deg F( x) =k,若对所有 x∈ U,有 deg F( x)≥ k,则 F称为带缺损 U的上限半 - k-因子 ;若对所有 x∈U,有 deg F( x)≤ k,则 F称为带缺损 U的下限半 - k-因子 .本文证明了若 k| V( G) |是偶数 ,| V( G) |≥ k+ 2 ,对 V( G)的任一基数为 k+ 2的子集 U,如果对任意 e∈ E( G) ,G都有一个带缺损 U的上限半 - k-因子含 e,则 G是 k-覆盖的 ;若 k≥ 2是一个偶数 ,| V( G) | >2 k+ 4 ,对V( G)的任一基数为 k+ 3的子集 U,如果对任意 e∈E( G) ,G有一个带缺损 U的上限半 - k-因子含e,则 G是 k-覆盖的 ;还证明了若 k| V( G) |是偶数 ,| V( G) |≥k+ 4 ,对 V( G)的任一基数为 3的子集U,如果对任意 e∈E( G) ,G都有一个带缺损 U的下限半 - k-因子含 e,则 G是 k-覆盖的 .

L et Gbe a2 - edge connected graph,and letk≥ 1be an integer.L et Ube a sub- set of V(G) ,and let F be a spanning subgraph of Gsuch thatdeg F(x) =kfor allx∈ V(G) - U .If deg F(x)≥ k for all x∈ U ,then F is called an upper semi- k - regular factor with defectset U ,and ifdeg F(x)≤ kfor all x∈ U ,then F is called a lower semi- k - reg- ular factor with defect set U .We show thatifk|V(G) |is even,|V(G) |≥ k +2 ,and for any subset U of cardinalityk +2 of V(G) ,and for anye∈ E(G) ,Ghas an upper semi- k - regularfactor with defectset Ucontaining e,then Gisk - covered.We also show thatifkis even,|V(G) |>2 k +4,and for any subset U of cardinality k +3of V(G) ,and for any e∈ E(G) ,G has an upper semi- k - regular factor with defectset U containing e ,then G isk - covered.Further,we show thatifk|V(G) |is even,|V(G) |≥ k+4,and for any subset U of cardinality3of V(G) ,and for anye∈ E(G) ,Ghas a lower semi- k - regular factor with defectset U containing e,then G isk - covered.