Tutte类型条件刻画与图因子  

Characterization of the Tutte-type condition and graph factors

作　　者：鲁红亮[1] 王国亮 于青林 Hongliang Lu;David G.L.Wang;Qinglin Yu

机构地区：[1]西安交通大学数学与统计学院,西安710049 [2]北京理工大学数学与统计学院,北京100081 [3]Department of Mathematics and Statistics,Thompson Rivers University,Kamloops V2C0C8,Canada

出　　处：《中国科学：数学》2024年第11期1821-1828,共8页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:12271425和12171034)资助项目。

摘　　要：令G是一个连通图.令f:V(G)→Z^(+)是一个整值函数,用J_f(v)表示由f(v)及所有不超过f(v)的奇数所组成的集合,J_f~o(v)表示由所有不超过f(v)+1的奇整数所组成的集合.本文证明如下结果:对于任意S⊂V(G),有o(G-S)≤f(S),当且仅当对于任意H∈H,G有一个H-因子,这里H={H:V(G)→2N|对于任意v∈V(G),有H(v)∈{J_f(v),J_f~o(v)}}.这是Akiyama和Kano(2011)所提出公开问题的新刻画.此外,本文依据图因子刻画了图的坚韧度条件.Let G be a graph.For any vertex v∈V(G)and any function f:V(G)→Z^(+),denote by Jf(v)the set consisting of the integer f(v)and all positive odd integers less than f(v),and by Jo f(v)the set of positive odd integers no greater than f(v)+1.In this paper,we show that a graph G satisfies the Tutte-type condition o(G−S)≤Σ_(v∈vs)S f(v)for any nonempty set S⊂V(G);if and only if G contains an H-factor for any H∈H,where H={H:V(G)→2^(N)|H(v)∈{J_(f(v));J^(o)_(f(v))}for each v∈V(G)}:This is a new characterization on the open problem proposed by Akiyama and Kano(2011).Moreover,we also characterize toughness conditions in terms of graph factors.

关 键 词：Tutte条件 度约束因子 坚韧度 

分 类 号：O157.5[理学—数学]