拟无爪图的性质

Properties of a quasi-claw-free graph

讨论了比无爪图更广泛的图——拟无爪图,得到了以下两个结果:(ⅰ)若图G是拟无爪图,且满足ω(G-S)≤t(G),则2t(G)=κ(G).(ⅱ)若图G是拟无爪图,对于任意的控制集D及任意t∈D,至多存在3点u1,u2,u3∈(V-D)满足N(ui)∩D={t}(i=1,2,3),则γ(G)=i(G),该结果是最好可能的.以上结果扩展了无爪图的相应结果.

The properties of quasi-claw-free graphs were discussed, which are larger than claw-free graphs. The following two resuhs were obtained： if G is a quasi-claw-free graph, then （ i ） 2t（G）=κ（G）, where ω（G-S）≤t（G） （ ii ） For every dominating set D and each t E D, there are at most three vetices u1, u2, u3 ∈ （ V - D） satisfying, N（ ui ）∩D={t}（i=1,2,3）, then γ（G） = i（G）. This result is the best possible. These results extend the corresponding resuhs in a claw-free graph.