共查询到18条相似文献,搜索用时 109 毫秒
1.
2.
《淮阴师范学院学报(自然科学版)》2016,(3):189-192
对于图的任一顶点集的划分,并使每个划分的导出子图均为无圈图的最小的划分基数称为图的顶点荫度.对于图G的每个顶点给定一个列表基数至少为k的颜色集合,对于图的任一染色,若每个顶点的颜色均选择与其关联的颜色集,使得每种颜色类的导出子图是一个无圈图的最小的基数k称为图的列表点荫度.证明了每个无6圈和相交i,j-圈(i,j∈{3,4})的非负特征图的列表顶点荫度为2,即为4列表可选色. 相似文献
3.
图的线性点荫度是对它的顶点进行染色所用的最少颜色数,同时使得染同一种颜色的点集所导出的子图,它的每个分支均为路.本文完全确定了完全多部图的线性点荫度,给出了笛卡儿积图的线性点荫度的一个上界,得到了一些特殊图( 如路,圈和完全图) 的笛卡儿积图的线性点荫度. 相似文献
4.
图G的顶点集V(G)划分为一些子集,使得每个子集的导出子图是0线森林(即每个分支是路)的最小子集数叫图G的点线荫度,记为v|a(G).Poh K S证明了任何平面图的点线荫度最多是3.Matsumato M给出了图的点线荫度的上界,即v|a(G)≤[△(G)/2].这里△(G)是G的最大度.本文给出了完全n部图的点线荫度计算公式,同时也给出了任意图的点线荫度的精确上下界. 相似文献
5.
6.
7.
8.
设图G为最大度为Δ的平面图。图G的线性2-荫度是将图G的边集合分解成k个线性森林的最小整数k,其中每个分支树为长至多为2的路,记为la2(G)。得到了平面图线性2-荫度的上界:若Δ≡0,3(mod 4),则la2(G)≤「Δ/2棢+8;若Δ≡1,2(mod 4),则la2(G)≤「Δ/2棢+7。 相似文献
9.
整数距离图G(D)以全体整数为顶点集,顶点u,v相邻当且仅当|u-v|∈D,其中D是一个正整数集.对于m>3,设Dm,3={1,2,…m}\{3},得到了G(Dm,3)的点荫度的上界和下界并决定出了它在某些m上的确切值. 相似文献
10.
整数距离图G(D)以全体整数为顶点集,顶点u,v相邻当且仅当|u—v|∈D,其中D是一个正整数集.对于m〉3,设Dm,3={1,2,…m}\{3},得到了G(Dm,3)的点荫度的上界和下界并决定出了它在某些m上的确切值. 相似文献
11.
吕长青 《华东师范大学学报(自然科学版)》2015,2015(1):131-135
通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度. 相似文献
12.
图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]. 相似文献
13.
图G的平方图G2是以V(G)作为它的点集,两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了:若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12?;特别地,一棵树T的平方图T2的点荫度va(T2)=「Δ+12?. 相似文献
14.
15.
整数距离图以全体整数作为顶点集,顶点u、υ相邻当且仅当|u-υ|∈D,其中D是一个正整数集.对于m〉3,令Dm=[1,m]/[1,3].本研究得到了G(Dm)的点荫度. 相似文献
16.
王志坚 《苏州科技学院学报(自然科学版)》1995,(2)
以a(G)a1(G)分别记图G的点荫度、边荫度,对任意P阶非平凡简单图G及其补图,本文得到以下Nordhaus-Gaddum类型不等式:|x|、|x|分别表x之上整数、下整数。而且,对于每一正整数p,(i)、(ii)、(iv)式下界和(iii)式上界均可达到。 相似文献
17.
董进全 《内蒙古大学学报(自然科学版)》1992,23(4):465-467
图G的曼荫度vas(G)定度为对G进行项点着色且使得G中同色顶点导出的子图的每个连通分支都为星时所需的最少色数,本文证明了平面图和外平面图的曼荫度的平凡上界事实上也是最好的上界. 相似文献
18.
Halin图和Series—Parallel图的星荫度 总被引:1,自引:1,他引:0
证明了:(1)所有Halin图的星荫度为3,和(2)所有Series-Parallel图的星荫度小于等于3。 相似文献