爪与圈可扩性

CLAWS AND CYCLE EXTENDABILITY

图Ｇ中一个与Ｋ１，３同构的导出子图叫做Ｇ的一个爪，爪中的３度顶点叫它的爪心．用ｒ（ｖ）表示图Ｇ中所有以顶点ｖ为爪心的不同爪的数目．证明了阶数≥３的连通、局部连通图Ｇ，如果Ｇ的爪心集合Ａ是点独立集，且ｖ∈Ａ，ｒ（ｖ）≤ｄ（ｖ）－３。

In a graph G ,an induced subgraph isomorphic to K 1,3 is called a claw of G The vertex with degree 3 in a claw is called a claw centre.The number of claws of G with the claw centre v is denoted by r(v) .The following result is proved: Let G be a connected,locally connected graph.If the set of claw centres of G is independent and r(v) ≤ d(v) -3 for every v∈V(G) ,then G is fully cycle extendable.