共查询到10条相似文献,搜索用时 62 毫秒
1.
2.
关于θ-图的邻点可区别全染色 总被引:10,自引:1,他引:9
u,v两点间连三条内部不相交的路且至多有一条长度为1的图,称为θ-图.设G是阶至少为2的连通图,k是正整数,f是V(G)∪E(G)到{1,2,3,…,k}的映射,对任意u∈V(G),记C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)}.如果:1)对任意uv,vw∈E(G)u≠w,有f(uv)≠f(vw);2)对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);3)对任意uv∈E(G),有C(u)≠C(v),那么称f为G的k-邻点可区别全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别全染色}为G的邻最可区别全色数,记作Xat(G).本文得到了θ-图的邻点可区别全染色。 相似文献
3.
对简单图G(V,E),若存在自然数k(1≤k≤△(G))和映射f:E(G)→{1,2,…,k}使得对任意相邻两点u,(υ)V(G),u(υ)E( G),当d(u)=d(υ)时,有C(u)=C(υ),则f为G的k-邻点可约边染色,其所用最多染色数称为图G的邻点可约边色数,本文得到了若干广义Mycielski图的邻点可约边染色数. 相似文献
4.
设G=(V,E)是一个图,一个函数f:E→-1,+1如果∑f(e)≤0 e∈E[v]对于至少k个顶点v∈V(G)成立,则称f为图G的一个反符号星k控制函数,其中E(v)表示G中与v点相关联的边集.图G的反符号星k控制数定义为γrkss(G)=max{∑f(e) e∈E│f为图G的反符号星k控制数}。得到了一般图的反符号星k控制数的若干上界,对文[6]中的结果进行了推广,还确定了路Pn和圈Cn的反符号星k控制数。 相似文献
5.
对图G(V,E),一正常k-边染色f称为图G(V,E)的k-邻强边染色,当且仅当任意uv∈E(G),有f[u]≠f[u],其中f[u]={f(uw)|uw∈E(G)},并称x′。(G)=min{k|存在G的一k-ASEC}为G的邻强边色数.研究了△(G)≥5的伪-Halin图的邻强边色数,并通过归纳法证明了对△(G)=5的伪-Halin图G,有5≤x′as(G)≤6.如果E(G[V△])≠Ф,则,x′as(G)=6.并提出猜想:对|V(G)|≥6的连通图G(V,E)有△(G)≤x′as(G)≤△(G) 2.其中△(G)为G的最大度. 相似文献
6.
C23n,C24n邻点可区别的全染色 总被引:5,自引:1,他引:4
设G(V,E)是阶数不小于2的简单连通图,n是自然数,V∪E到{1,2,…,k}的映射f满足Vuv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);А↓uv,uw∈E(G),(v≠w),f(uv)≠f(uw);А↓uv∈E(G),G(u)≠C(v).其中C(u)=f(u)∪{f(uv)|uv∈E(G)}.,f称为G(V,E)的一个邻点是可区分的全染色法,简记为k-AVDTC.其中最小的k称为G的邻点可区别的全色数。G^2是G再加上G中点间距离为2时连边后的图.本文得到了3n、4n阶圈C3n^2,C4n^2邻点可区别的全色数。 相似文献
7.
《兰州交通大学学报》2017,(6)
一个有q边的连通图G的一个标号是一个映射f,使得图G顶点分配给不同的整数,如果图G的所有边标号集等于{1,2,…,q},则称f是图G的一个优美标号,称G是优美图.图的优美标号可用于解决Rosa分解猜想,这就需要证明每一棵树是优美的,然而它又成为一个未解决的难题.已知树的二分全优美标号可得到一些逼近优美树猜想的结果,因此可考虑一个弱于优美树猜想的猜想:一棵被删除所有叶子后余图恰是一棵毛毛虫树的树T是二分全优美的.树T的一个二分标号是一个双射f,且存在一个正整数k,使得f(u)≤k≤f(v),则顶点u和v属于树T的顶点集的二部分划分的不同部集.定义了全优美标号空间和k?二分全优美树,证明了一类二分全优美树,给出一些大型二分全优美树的构造方法. 相似文献
8.
设G为一简单图,本文证明了:如果G的线图L(G)为哈密顿的,且在G中存在两个顶点u、υ∈V(G),满足d(u) d(v)≥f(n)(f(n)为整数),那么L(G)中存在k个分支的2-因子,其中1≤k≤「f(n)-2/4」,且说明了当f(n)≤n时所给的结果为最好可能的,这个结果是对R.J. Gould和E.A. Hynds[4]的结果的推广和加强. 相似文献
9.
姚明 《兰州交通大学学报》2003,22(6):4-6
图的L(2,1)—标号问题来自频率分配问题并且是NP—完全性问题。得到:(Ⅰ)G是p个顶点的简单图,对正整数k≥3,当p≥2k^2和△≥p/k时,有L(G)≤△^2。(Ⅱ)△(G)表示图G的最大度,则L(G)≥△(G) 1。(Ⅲ)若V(G)可划分为独立集V1,V2,…,Vk,且V(G)=U^ki=1Vi及Vi∩Vj=Ф,i≠j,则L(G)≤p k-2。 相似文献
10.