共查询到20条相似文献,搜索用时 46 毫秒
1.
孔立 《烟台师范学院学报(自然科学版)》2005,21(2):106-108
双外平面图是一个平面图,它可以嵌入到平面上并使得它的顶点出现在两个面的边界上.证明了对于最大度至少是6的双外平面图,有Xef(G)≤△(G) 1,其中△(G)是G的最大度. 相似文献
2.
王维凡 《辽宁大学学报(自然科学版)》1993,20(2):1-6
平面图G(V,E,F)的点面全色数X_e(G)是使得集合V(G)∪F(G)中相邻和相关联的元素均染为不同颜色的最少颜色数。本文证明了:若G是三角剖分图,则4≤X_e(G)≤6。 相似文献
3.
许宝刚 《山东大学学报(理学版)》1996,(4)
图G的全色数x_T(G)是使得VE(G)中相邻接或相关联的元素均着不同颜色的最少颜色数。证明了:如果ν(G)=ν(H),存在υ(?)V(G),υ'(?)V(H)使得G~c—υ和H~c—υ'都含有完美对集且△(G)=△(H)并存在e(?)E(G—υ),e'(?)E(H—υ'),使得G—e和H—e'都是第一类图,或△(G)<△(H)且存在e(?)E(H—υ')使得H—e'是第一类图,则x_T(GVH)≤△(GVH)+2g. 相似文献
4.
图G的k-全染色是用k种颜色对图G的V(G)∪E(G)中的元素进行着色, 使得相邻或者相关联的两个元素染不同的颜色, 图G的全色数是使G存在k-全染色的最小整数k. 对最大度为Δ的平面图, 如果(1),Δ(G)≥5且任何点至多关联一个长度至多为5的圈, 或者(2),Δ≥4, 不含3-圈并且任何点至多关联一个长度至多为6的圈, 则它的全色数为Δ(G)+1。 相似文献
5.
设G是一个简单图,其顶点集为V(G)而边集为E(G).图G的一个k-染色是指顶点集V(G)到色集{1,2,…,k}的一个映射.如果图G的一个点染色使G的每个极大团所有颜色均出现(这里不要求邻点染色不同),则称该染色为图G的全色极大团染色.而G的全色极大团色数是指能进行全色极大团染色的最大颜色数,记为χmaxcT(G). 相似文献
6.
证明了如下结果:一个简单连通图G的全色数和列表全色数都为△+1,如果它存在一个支撑子树T使得△(G)≥6和△(G\E(T))≤2,或者△(G)≥4和△(G\E(T))≤1。 相似文献
7.
8.
设G=(V,E)是一个无向图,如果S V,对于任v∈V,均有v或者它的一个邻点在S-v中没有邻点,则称S为G的一个全无赘集.G中含点数最多(少)的极大全无赘集,称为上全无赘集(全无赘集).G的(上)全无度△(G)给出全无赘数的上界,IRt(G)≤n/(1 (△ 1)δ/(△-1)/△))而且这个界可达. 相似文献
9.
用△(G)表示图G的顶点最大度.对平面图,当△(G)≥11时,已证明Vizing和Behzad的图的全色数猜想(TCC)是正确的.运用Dischrge方法证明了最大度为9且不含4-圈的平面图的全色数等于10. 相似文献
10.
林年锋 《南京师大学报(自然科学版)》2004,27(4):28-31
图G的平方图,记作G^2,是一个以原图的顶点集为顶点集,若原图中两点的距离不大于2则连以边所成的图.本文确定了圈的平方图的色数.对于外部平面图,得到以下结论:设G是一个最大度为△(G)的简单连通外部平面图,G≠C5.则x(G^2)≤△(G) 2. 相似文献
11.
谢德政 《重庆工商大学学报(自然科学版)》2005,22(1):4-5
设G是一个图,G的全着色是一个映射π:V(G)YE(G)C,使得相关联或相邻的元素着不同色;G的所有全着色中,使得色数的最小者,称为G的全色数,记为χT(G);得到了几个特殊图的全色数 相似文献
12.
设计了对任意自然数n(n≥3)且n=1(mod 2)的奇圈图的边幻和标号和超边幻和标号算法,证明了得到的所有奇圈图既是边幻和图,也是超边幻和图. 相似文献
13.
14.
关于几类特殊图的Mycielski图的邻点可区别全色数 总被引:8,自引:6,他引:2
设G是一个简单图,f是一个从V(G)∪ E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是G的正常全染色且u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设xat(G)=min{k|G存在k-AVDTC},则称xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数. 相似文献
15.
关于图K2n+1-E(2 K2)的邻点可区别全色数 总被引:7,自引:6,他引:1
用K2n 1-E(2K2)表示2n 1阶的完全图删掉两条不相邻的边所得到的图,给出了图K2n 1-E(2K2)的邻点可区别全色数. 相似文献
16.
不同方法测定污水中总氮总磷的比较研究 总被引:2,自引:0,他引:2
传统的总氮(TN)总磷(TP)检测方法为碱性过硫酸钾氧化-紫外分光光度法,现针对目前国内总氮和总磷联合消解测定的试验条件差异较大的问题,通过对几种方法的比较,优化了总氮、总磷联合消解测定的试验条件,建立了一种准确、快速的分析方法。 相似文献
17.
设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…,k)的映射f满足:对任意uυ,υw∈E(G),u≠w,有f(uv)≠f(υw);对任意uυ∈E(G),有,(u)≠,(υ),f(u)≠f(uυ),f(υ)≠f(uυ);那么称f为G的k-正常全染色,若,还满足对任意uυ∈E(G),有C(u)≠C(υ),其中C(u)={(u))∪{f(uυ)|uυ∈E(G),υ∈V(G)),那么称,为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色)为G的邻点可区别的全色数,记作xat(G).本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数. 相似文献
18.
侯新民 《中国科学技术大学学报》2006,36(6):604-606
设G为n阶连通图,集合S称为图G的全控制集,如果V(G)的每个顶点都和S中某点相邻。图G的全控制数,记为γt(G),是图G的全控制集的最小基数。证明了对阶数n≥3且T≠K1,n-1的树T,γt(T)=min{(2n/3),n-l,[n/2]+l-1},这里l表示树T中叶子的数目。 相似文献
19.
联图 Ws∨Km,n的邻点可区别全色数 总被引:1,自引:0,他引:1
图的邻点可区别全染色(AVDTC)数为χat(G),有猜想:xat(G)≤Δ(G)+3. 联图 Ws∨Km,n的邻点可区别全色数被确定为χat(Ws∨Km,n)=Δ( Ws∨Km,n)+1或Δ(Ws∨Km,n)+2. 相似文献
20.
全染色猜想在分数全染色的意义下是成立的,在此基础上,我们进一步研究了几类特殊图的分数全色数,如圈、完全图、完全二部图、平衡完全r-部图。 相似文献