给定一个图G=(V,E)及其顶点集V的互不相交的非空子集A1,A2,···,Ar,如果存在互不相交的圈C1,C2,···, Cr满足Ai⊆V(Ci)(i=1,2,···,r)并且C1∪C2∪···∪Cr生成G,则称G是关于子集A1,A2,···,Ar生成可圈的。如果G关于V的任意r个互不相交的子集A1,A2,···,Ar 都是生成可圈的,则称G是r-生成可圈的。进一步,如果G对于任意满足|A1∪A2∪···∪Ar|≤t的互不相交的点子集A1,A2,···,Ar是r-生成可圈的,则称G是阶数为t的r-生成可圈图。本文中,我们证明了：如果G是顶点数n≥3r+1,边数m≥(n−1)(n−2)2+k+r−2(r≥1,3≤k≤n−r+1)的图,则G是阶数为k+r−3的r-生成可圈图。本文将文献[1]中r=2的结果推广到了一般的情形。%Given a graph G = (V,E) and mutually disjoint nonempty subsets A1,A2,...,Ar of V, we say that G is spanning cyclable with respect to A1,A2,··· ,Ar if there exist mutually disjoint cycles C1,C2,··· ,Cr such that Ai⊆V(Ci) for i=1, 2, · · · , r and C1∪C2∪· · ·∪Cr spans G. And G is r-spanning-cyclable if G is spanning cyclable with respect to A1,A2,...,Ar for every such mutually disjoint nonempty subsets of V. Moreover, we say that G is r-spanning-cyclable of order t if G is spanning cyclable with respect to A1,A2,··· ,Ar for any r nonempty mutually disjoint subsets A1,A2,··· ,Ar of V such that|A1∪A2∪· · ·∪Ar|≤t. In this paper we prove if G is a graph of order n≥3r+1 (r≥1) and has at least (n−1)(n−2) 2+k+r−2 edges for 3≤k≤n−r+1, then G is r-spanning-cyclabe of order k+r−3. Our result extends the result obtained by Cheng et al. in [1] for r=2.
展开▼
