T_3-受限图的完全圈可扩性

Fully Cycle Extensibility of T_3-Confined Graphs

剖分K1,3的一边所得到的图形叫T3,其中3度顶点x0叫做T3的中心。如果图G中的任意一个与T3同构的子图的三个一度顶点xi(i=1,2,3)之间至少有一条边,则称图G为T3-受限图。如果G满足:(1)G的每个顶点都在三圈上,(2)对G中的任意一个圈C,只要V(C)<V(G),就存在G的圈C′,C′满足V(C)V(C′),且│C│′=│C│+1,则称G是完全圈可扩的,C′为C的扩圈。文中证明了:连通、局部连通的T3-受限图是完全圈可扩的。

A graph got of one edge of K1,3 , which is called T3 ,the vertex xo （ d（xo） = 3 ） is called centre of T3 . Every subgraph in graph G isomorphic to T3 , if there is at least one edge among three vertices xi （ d（xi ） = 1, i =1,2,3）, , then G is called T3 -confined graph. arbitary v∈V（G）, if G[N（v）] is k-connected, then G is called k-connected. If G satisfies： （1） arbitary u∈V（G）, u is in a 3-cacle, （2） arbitary C in G, as long as V（C） belong to V（G）, then exists cycle C＇ in G, C＇ satisfies V（C） belong to V（C＇） and ｜C＇｜=｜C｜＋1, then G is fully cycle extensible, C＇ is called extended pathe of C, It shows that： every connected, locally connected, T3-confined graph is fully cycle extensible.