共查询到20条相似文献,搜索用时 781 毫秒
1.
孙志人 《南京师大学报(自然科学版)》1995,18(1):35-40
设G是k-连通无爪图,S是G的子图,G中过S所有顶点的路称为S-路,证明了:若a3(S)≤k+1,则G含S-路,这里a3(S)为S的在G中两两离至少为3的顶点的最大数目,推广了如下结论:若a(G^2)≥k+1,则G是可迹的,这里G^2为G的平方图。 相似文献
2.
证明了如下结果:(1)若G是2-连通的(K1,3,P5,B)-自由图,或2-连通的(K1,3,Z2,P5)-自由图,则G是哈密顿图,(2)若G是3-连通的(K1,3,Z1)-自由图,或3-连通的(K1,3,Z2,P5)自由图,或3-连通的(K1,3,P5,B)-自由图,则G是哈密顿连通的。 相似文献
3.
令阿Ar=(a_1,a_2,…,a_r),其中整数a_i≥2,r≥1.所谓图G的Ar着色即对 图G的边用不同的颜色c_1c_2,…,c_r着色,使得没有一个a_i个顶点的完全子 图的所有边都着色c_i(i=1,2,…,r).令HlN为具有N个顶点但不包含l个顶 点的完全子图的图的集合,N(Ar,l)表示G∈HlN但不能被 A 着色的图具有的 最少顶点数。本文定义一种临界图,并在此基础上利用H5(N-1)的临界图构造H5N 的临界图。通过证明H5(12)的临界图均能(3,3)着色,证明H5(12)中的图均能(3,3) 着色,进而得出:13<N((3,3),5)<18,优于前人得出的10<N((3,3),5)<18的结 果. 相似文献
4.
5.
娄定俊 《中山大学学报(自然科学版)》1995,34(2):18-21
设G是具有二分类(X,Y)的2连通等部偶图。如果对G中每一个顶点v,H是G中与v距离为2和3的所有顶点导出的子图,并且对于g中每一个与v距离为3的顶点u,u在H中的度数d_H(u)不小于距离v为2的顶点的数目减去(dG(v)-2),则G是Hamilton图。其中d_H(u)的下界不能改进。 相似文献
6.
关于图的第二大根的极限点 总被引:1,自引:0,他引:1
设G为无孤立点的简单图,λ2(G)为G的第二大特征根。该文给出区间(1/3,√33-5/2)内的所有第二大根的极限点-(5k-1)+√33k^2+14k+1/2(k-3) 相似文献
7.
对任意简单图G,△(G)和XT(G)分别表示G的最大度和全色数。证明了当△(G)≥4时,2-退化图G的全色数XT(G)=△(G)+1。 相似文献
8.
张秀英 《东北师大学报(自然科学版)》1997,(2):8-14
利用不可约路的概念,证明了当Ps是不可约的路时,Kn-E(kPs∪rK3)是色唯一的图,其中设Kn-E(G)表示从完全图Kn中删去一个和G同构的子图的所有边而得到的图,s≠4,且ks+3r=n,k3是有3个顶点的完全图,同时给出了三类新的色等价图簇。 相似文献
9.
系列—平行图的列表染色 总被引:2,自引:0,他引:2
吴建良 《山东大学学报(自然科学版)》2000,35(2):144-149
系列-平行图是没有子力与K4同胚的图。设G为一个系列-平行图。如果对任意的边e∈E(G),有f(e)≥max(4,Δ(G)),则G是f-可列表染色的同时还确定了所有系列-平行图的边色数。 相似文献
10.
11.
A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa( G),is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k + 1. The k-star arboricity of a graph G,denoted by sak( G),is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2( G) ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T)/k]t≤ sak( T) ≤[Δ( T)- 1/K]+1,where Δ( T) is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak( T) ≤m for any tree T and any positive integers m and k. 相似文献
12.
13.
董进全 《内蒙古大学学报(自然科学版)》1992,23(4):465-467
图G的曼荫度vas(G)定度为对G进行项点着色且使得G中同色顶点导出的子图的每个连通分支都为星时所需的最少色数,本文证明了平面图和外平面图的曼荫度的平凡上界事实上也是最好的上界. 相似文献
14.
15.
图的线性点荫度是对它的顶点进行染色所用的最少颜色数,同时使得染同一种颜色的点集所导出的子图,它的每个分支均为路.本文完全确定了完全多部图的线性点荫度,给出了笛卡儿积图的线性点荫度的一个上界,得到了一些特殊图( 如路,圈和完全图) 的笛卡儿积图的线性点荫度. 相似文献
16.
图G的全图T(G)是以V(G)∪E(G)为顶点集的一个图,其中两个顶点相邻当且仅当它们在图G中对应的元素是相邻或关联的.图G的全荫度ρ"(G)是将其全图的顶点集V(T(G))划分为最少的子集数,使得每个子集在全图中的导出子图是一个森林.列表全荫度硝(G)是全荫度概念的列表染色的版本.本文证明了:(1)对完全图‰,ρ"(Kn)=「(n+1)/2];(2)对完全二部图Kn,n,ρ"(Kn,n)=「(n+2)/2];(3)对Halin图G,ρl"(G)≤「(△(G)+2)/2]. 相似文献
17.
卢鹏丽 《宁夏大学学报(自然科学版)》2009,30(3):220-222
如果与图G同谱的图都与G同构,则称图G由它的谱确定.重合星图K1,q的中心点和圈图Cn的一个点得到章鱼图.证明了这一类单圈图由Laplacian谱确定. 相似文献
18.
唐廷载 《西华师范大学学报(哲学社会科学版)》2001,(3)
众所周知 ,星S3=K1,3是一个无有限niche数的图 .而本文的研究证明 :S3与许多图类的并图都是有有限niche数的图 . 相似文献
19.
吕长青 《华东师范大学学报(自然科学版)》2015,2015(1):131-135
通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度. 相似文献
20.
熊黎明 《江西师范大学学报(自然科学版)》1994,18(4):343-346
该文讨论了无爪图的顶点划分数,给出了完全n部图的顶点划分数的计算公式,最后证明了任意图的点线荫度不大于它的边线荫度且不等式是精确的. 相似文献