Sm∨Fn的全色数

设G(V,E)是阶数至少是2的简单连通图,k是正整数,若f是从V(G)∪E(G)到{1,2,…,k}的一个映射,使得:对于任意的uv,vw∈E(G),u≠w,有f(uv)≠f(vw);且对于任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的一个k-全染色(简记成k-TC of G).而χt(G)=min{k|k-TC of G},称为G的全色数.设G和H是点边都不相交的简单图,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)},则称G∨H是G与H的联图.给出m 1阶星和n 1阶扇的联图的全色数.     

D（pn）图的邻点强可区别全染色

设f为用k色时G的正常全染色法,对任意的边uv∈E（G）,其端点的色集合满足C（u）≠C（v）,其中C（u={f（u））U{f（v）｜uv∈E（G））U{f（uv）}uv∈E（G））,则称,是G的k邻点强可区别的全染色法（简记作k-AVSDTC）,且称xast（G）=min{k}G的所有k-AVSDTC}为G的邻点强可区别全色数．本文得到D（pn）图的邻点强可区别全色数,其中pn为n阶路．     

一类Hamilton图

若P[u,v]是2连通无爪图G的最长路,设dp(xβ,xα)=︱P[xβ,xα]︱-1(xβ相似文献   

完全二部图K5，n的点可区别IE-全染色

设G是简单图,图G的一个k-点可区别IE-全染色（简记为k-VDIET染色）f是指一个从V（G）∪E（G）到{1,2,…,k}的映射,且满足：A↓uv∈E（G）,有f（u）≠f（v）;A↓u,v∈V（G）,u≠v,有C（u）≠C（v）,其中C（u）={f（u）}∪{f（uv）｜uv∈E（G）}。数min{k}G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χut^ie（G）。本文给出了完全二部图K5,n（n≥6）的点可区别IE-全色数。     

D(p_n)图的邻点强可区别全染色

设f为用k色时G的正常全染色法,对任意的边uv∈E(G),其端点的色集合满足C(u)≠C(v),其中C(u)={f(u)}∪{f(v)|uv∈E(G)}∪{f(uv)|uv∈E(G)},则称f是G的k邻点强可区别的全染色法(简记作k-AVSDTC),且称χast(G)=min{k|G的所有k-AVSDTC}为G的邻点强可区别全色数.本文得到D(pn)图的邻点强可区别全色数,其中pn为n阶路.     

C_m×K_n的邻点可区别全染色

设G(V,E)是阶数至少为2的简单连通图,k是正整数,V∪E到{1,2,3,…,k}的映射f满足:对任意uv,vw∈E(G),u≠w,有f(uv)≠f(vw);对任意uv∈E(G),有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv);那么称f为G的k-正常全染色,若f还满足对任意uv∈E(G),有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G),v∈V(G)},那么称f为G的k-邻点可区别的全染色(简记为k-AVDTC),称min{k|G有k-邻点可区别的全染色}为G的邻点可区别的全色数,记作Xat(G).本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数.     

图的最长路的一个性质

本文给出了图的最长路的一个性质:设G是有n个点的2-连通图,如果对于任一对使d（u,v）=2的点u和v而推出max{d（u）,d（v）}≥c/2（3≤c≤n）,那么存在一条最长路μ=v_1v_2…v_r,且min{d（v_1）,d（v_r）}≥c/2。由此可得到图中圈长性质的一个较简单的证明。     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G^＊满足V（G^＊）=V（G）,E（G^＊）=E（G）∪{uv：uv∈E（G）,且J（u,v）≠φ},这里J（u,v）={w∈N（u）∩N（v）,N（w）（∈）N[u]∪N[v]}.本文利用插点方法,给出了关于k,或（k＋1）-连通（k≥2）图G是哈密尔顿的,1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是在图G中关于^k∑i=1｜N（Yi）｜＋b｜N（y0）｜与n（Y）的不等式,这里Y是图G的部分平方图G^＊的任一独立集,对于i∈{1,2,…,k},Yi={yi,yi-1,…,yi-（b-1）}（∈ ）Y（yj的下标将取模k）;b是一个整数,且0＜b＜k＋1;n（Y）=｜{v∈V（G）,dist（v,Y）≤2}｜.     

点可区别全色数的一个上界

设G是简单图，f是从V（G）UE（G）到{1,2，…，k）的一个映射．对每个u∈y（G），令c（u）={f（u）}v∈V（G）,uv∈ E（G）}．如果，是k-正常全染色，且对任意u，v∈V（G）（u≠v），有c（u）≠c（v），那么称f为图G的k-点可区别全染色（简记为k-VDTC）．数χvt（G）=min{k｜G-有k—VDTC}称为图G的点可区别全色数．通过应用概率方法，证明了对任意最大度A≥2的图G，χvt（G）≤32（△＋1）．     

图K2n\E（Fm）（n≥4,m≥2）的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(Fm)(n≥4,m≥2)的点可区别边色数.     

图K_(2n)\E(F_5)(n≥13)的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(F5)(n≥13)的点可区别边色数.     

极大3等周边连通图的充分条件

k等周边连通度是一个比边连通度更可靠的网络可靠性参数。 连通图G的k等周边连通度定义为γk(G)=min{［X,X-］:XV(G),X≥k,X-≥k},其中X-=V(G)＼X。令βk(G)=min{［X,X-］:XV(G),X=k}。图G是极大k等周边连通的如果γk(G)=βk(G)。令G是一个阶至少为6的连通图。本文证明了如果对于G中任意一对不相邻的顶点u,v,当u和v都不在三角形中时满足N(u)∩N(v)≥2;当u和v中至少有一个在三角形中时满足N(u)∩N(v)≥5,那么G是极大3等周边连通的。     

图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

一类单圈图的优美性和平衡性

设L为简单无向图G的一个顶点标号,L称为图G的优美标号,若L满足以下两条：（1）L为G的顶点集V到{0,1,2,…,｜EI｜}的一个单射;（2）由L’（e）=｜L（u）-L（v）｜（其中e=uv）决定的边标号L’是G的边集E到{1,2,…,｜EI｜}的一个双射．进一步,若存在正整数c,使得对每一个uv ∈ E（G）满足L（u）≤c〈L（v）或L（w）≤c〈L（u）,则称L为图G的平衡标号,其中c为平衡特征．主要研究一类单圈图的平衡性并给出相应的平衡标号及其特征．     

幂图的点强全色数

图G的一个正常全染色称为图G的点强全染色,当且仅当N[v]中任意元素都染有不同的颜色,其中N[v]={u}uu∈E（G）}U{u},图G的点强全染色所用颜色的最少数目称为图G的点强全色数．文章通过研究幂图t的结构性质,利用穷染、置换的方法,研究了幂图礴的点强全色数,并给出了一种具体的染色方案．     

奇圈、偶圈与轮的多重联图的邻点可区别E-全染色(英文)

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪E(G)到{1,2,…,k}的映射,如果uv∈E(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),其中,C(u)={f(u)}∪{f(uv)|uv∈E(G)},称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数,给出了奇圈、偶圈与轮的多重联图的邻点可区别E-全色数.     

恰有d个顶点带环的本原有向图的公共后继的界

如果存在正整数p,使有向图G中任一有序顶点对u和v都有长为p的途径,则有向图G称为本原有向图．设Pn(d)是n(n≥3)阶恰有d个顶点带环的本原有向图的集合,LG(k)是本原有向图G的k-公共后继(k-c．c．),2≤k≤n;又设L(n,d,k)=max|LG(k)|G∈Pn(d)|,由此得到了k-公共后继的界：n-[d/2]≤L(n,d,k)≤n-1,1≤d≤n．     

关于0-可旋转树

得到一种构造0-可旋转树的方法,证明了:若树T(n)和T(m)均为0-可旋转树,则每棵树(T(m)△T(n))uj(j∈[1,n])都是0-可旋转树.确定了无穷多0-可旋转树.