首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 34 毫秒
1.
图G的剖分是指把图G割分成一些只含孤立点或孤立边的分支,它是有序整效对(x,y),用符号D(G)表示。文章介绍了有关双圈图剖分的一些简单结果。  相似文献   

2.
研究了△(G)=3时Halin图的全色数,证明了(i)对于3-正则的Halin图G,有4≤xT(G)≤5;(ii)若将3-正则Halin图每边剖分一次,则对于剖分图M*有xT(M*)=4,这里△(G)表示图G的最大度数,xT(G)表示图G的全色数.  相似文献   

3.
-个图在某个曲面上的嵌入三角剖分该曲面.那么这个图是上可嵌入的,对于一个近三角剖分图却不一定是上可嵌人的.已经证明了平面近三角剖分图的上可嵌人性与独立边集之间的关系是:若G的对偶图G*有[1/2φ]个独立边集.那么图G的最大亏格γM(G)=(「)β(G)/2」-1.进一步讨论了平面近三角剖面图G有k个三角△1,△2,…,△k其上可嵌人的条件.  相似文献   

4.
关于两类平面图及相关图的L(2,1)-标号问题   总被引:2,自引:0,他引:2  
图G的L( 2 ,1) 标号是一个从顶点集V(G)到非负整数集的函数f(x) ,使得若d(x ,y) =1,则 |f(x) -f(y) | 2 ;若d(x ,y) =2 ,则 |f(x) -f(y) | 1 图G的L( 2 ,1)标号数λ(G)是使得G有max{f(v) :v∈V(G) } =k的L( 2 ,1)标号中的最小数k Griggs和Yeh猜想对最大度为Δ的一般图G ,有λ(G) Δ2 证明了对平面三角剖分图、立体四面体剖分图、平面近四边形剖分图 ,有上述猜想成立  相似文献   

5.
近三角剖分图的最大亏格与1-因子   总被引:4,自引:0,他引:4  
考察了平面近三角剖分图的最大亏格与独立边集之间的关系.设G*是平面近三角剖分图G的一个平面嵌入的几何对偶,如果G*有[1/2(ψ)]个独立边集,那么图G的最大亏格γM(G)≥[1/2β(G)]-1,这里(ψ)和β(G)分别表示图G在平面上嵌入的面数与G的Betti数.特别地,如果(ψ)=0 mod 2,即G有1-因子,则G是上可嵌入的.作为应用,证明了几个已知的结果.  相似文献   

6.
3-正则Halin图的剖分图的全色数   总被引:1,自引:0,他引:1  
研究了3-正则Halin图的剖分图G的全色数,证明了4≤xT(G)≤5,特别是当G的3-度点彼此不相邻时,有xT(G)=4,这里xT(G)表示G的全色数.  相似文献   

7.
连通图G的孤立断裂度isc(G)=max{i(G-S)-| S |:S∈C(G)},其中i(G-S)是G-S中的孤立点数,C(G)是G的点割集.文章研究了图与补图孤立断裂度的关系.  相似文献   

8.
图G的最长路的阶称为环游阶,记为τ(G)。顶点集V(G)的子集S称为图G的Pn-核,如果满足τ(G[S])≤n-1且V(G)-S的每一个顶点v都与G[S]中阶为n-1路的端顶点相连。把顶点集V(G)剖分成A,B两部分,使得τ(G[A])≤a和τ(G[B])≤b,此剖分称为图G的一个(a,b)-剖分。本文证明了对于n≤3g/2-1的正整数,任意围长为g的图都有一个Pn+1-核。并且还得到,如果τ(G)=a+b,其中1≤a≤b,图G的围长g≥2/3(a+1),那么G有一个(a,b)-剖分。  相似文献   

9.
平面图G(V,E,F)的点面全色数X_e(G)是使得集合V(G)∪F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文证明了:若G是三角剖分图,则4≤X_e(G)≤6。  相似文献   

10.
如果图G的每个极小点割(边割)都孤立一个点,则图G是超点连通(超边连通)的。图G的至少孤立一条边的边割称为限制性边割,其最小基数计作λ′(G)。当λ′(G)=ξ(G)时,称图G是λ′-最优,其中ξ(G)是图G的最小边度。本文给出了点积图是超点连通、超边连通、的一些充分条件。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号