Characterization of the Tutte-type condition and graph factors
鲁红亮 1王国亮 2于青林3
扫码查看
点击上方二维码区域，可以放大扫码查看
作者信息
1. 西安交通大学数学与统计学院,西安 710049
2. 北京理工大学数学与统计学院,北京 100081
3. Department of Mathematics and Statistics,Thompson Rivers University,Kamloops V2C0C8,Canada
折叠
摘要
令G是一个连通图.令f:V(G)→ Z+是一个整值函数,用Jf(v)表示由f(v)及所有不超过f(v)的奇数所组成的集合,Jof(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)∈ {Jf(v),Jop(v)}}.这是Akiyama和Kano(2011)所提出公开问题的新刻画.此外,本文依据图因子刻画了图的坚韧度条件.
Abstract
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 Jof(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∈Sf(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)→ 2N|H(v)∈{Jf(v),Jof(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.
万方数据