排序方式: 共有17条查询结果,搜索用时 31 毫秒
1.
2.
3.
设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 . 相似文献
4.
本文中我们用等秩变换证明了连通图G的所有生成树的邻接矩阵的秩中最大者就是图G线独立数的两倍。特别,我们给出了连通图G具有完美匹配的一个新的充要条件。 相似文献
5.
设G是一个图,并设n,k,r,a和b是整数且满足k≥1,k≤a<b和n≥3.对于G的给定的k-正则图H,如果G是K1,n-free图,且G的最小度至少是((n(a+1)+b-a-(k+1))/(b-k))「(ab+b-a-k)/(2(n-1))」-(n-1)/(b-k)(「(an+b-a-k)/(2(n-1))」)2-1,那么G有一个[a,b]-因子F使得E(H)(∈)E(F).类似地,也得到了关于图G有一个r-因子含有G中给定的k-正则子图的度条件.进一步,指出这些度条件是最佳的. 相似文献
6.
7.
关于图中子图的(n,k)—正交因子分解 总被引:1,自引:0,他引:1
设G是一个具有顶点集V(G)和边集E(G)的图.
设g和f是定义在V(G)上的两个整数值函数,使得g(x)f(x)对所有的点x∈V(G)都成立.如果G是一个(mg+n,mf-n)-图,1n<m2k,且g(x)2k-1对所有的点x∈V(G)都成立,则对任意给定具有|E(H)|=nk边的G的子图H,存在G的一个子图G′使G′有一个(g,f)-因子分解(n,k)-正交H. 相似文献
8.
设n,m和r是满足r≥2,n≥0,m≥3的整数,且当r是奇数时,假设r≥m-1.称一个图为K1,m-free,如果它不包含以Kt,m为导出的子图.称一个图G为一个(r,n)-临界图,如果在删去G的任意n个点后,剩下G的子图都有一个r-因子,设G是一个Kl,m-free的(n+1)-连通图,且阶为|G|以及r(|G|≥n)是偶数,证明了:如果G的最小度至少是r+n+m-1,阶|G|≥8r5+n,并且对V(G)的任意独立点集{x1,x2}都有|NG(x1)∪NG(x2)|≥(|G|+n)/2,那么G是一个(r,n)-临界图.关于G的最小度和|NG(x1)∪NG(X2)|的下界是紧的。 相似文献
9.
设G是一个图,并设g和f是定义在V(G)上的整值函数使得对所有的点x∈ V(G)均有g(x)≤ f(x).称一个图G是(g,f,H) -可扩的,如果在删除了任意一个同构于H的子图中所有点后,剩下G的子图有一个(g,f) -因子.该文给出了(g,f,H) -可扩图的特征.进一步,研究了(g,f,H) -可扩(H=nK1)的性质. 相似文献
10.
设$1\leq a<b, 0\leq k$是整数. 设$G$是一个含有$k$-因子$Q$且阶为$|G|$的图. 设\delta(G)$表示$G$的最小度, 且$\delta(G)\geq a+k$. 如果$Q$连通, 设$\varepsilon=k$, 否则设$\varepsilon=k+1$.证明:当$b\geq a+\varepsilon-1$时, 如果对$G$的任意两个不相邻的点$x$和$y$都有max$\{d_G(x),d_G(y)\}\geq {\rm max}\{{{a|G|} \over {a+b}},{{(|G|+(a-1)(2a+b+\varepsilon-2))} \over {b+1}}\}+k$, 那么$G$有一个$[a, b]$-因子$F$ 使得 $E(F)\cap E(Q)=\emptyset$. 这个度条件是最佳的, 条件$b\geqa+\varepsilon-1$不能去掉. 进一步,得到图存在含给定$k$-因子的$[a, b]$-因子的度条件. 相似文献