平方图的顶点PI指数

设G=(V,E)为简单连通图,称PI_(v)(G)=∑_(e=uv∈E)(n_(u)(e|G)+n_(v)(e|G))为G的顶点PI指数,其中n_(u)(e|G)表示图G中到边e=uv的端点u的距离小于到端点v的距离的顶点数,n_(v)(e|G)表示图G中到边e=uv的端点v的距离小于到端点u的距离的顶点数.用分类讨论法得到了圈和路的平方图的顶点PI指数.

平方图的2-距离和可区别边染色

为了进一步研究图的2-距离和可区别边染色的问题.利用组合分析法、反证法以及分类讨论的思想,得到了路、圈、C_(n)∧P_(m)、C_(m)∧C_(n)、C_(n)∧P_(m)∧C_(k)等5类平方图的2-距离和可区别边色数,结果表明这5类平方图的2-距离和可区别边色数均不超过Δ+2.

外平面图的平方图的点荫度

图G的平方图G2是以V(G)作为它的点集,两个点在G2中相邻当且仅当它们在G中的距离至多为2.证明了:若G是一个最大度Δ6的外平面图,则G2的点荫度va(G2)=「Δ+12﹁;特别地,一棵树T的平方图T2的点荫度va(T2)=「Δ+12﹁.

Kneser图KG(11,5)平方图的色数(英文)

Kneser图KG(n,k)的顶点集包括一个n元集的所有k元子集,其中的任意两个顶点相邻当且仅当它们对应的子集不相交.一个图G的平方图G2的顶点集与G的顶点集相同,在G2中两个顶点之间有边当且仅当它们在G中的距离不超过2.通过理论分析和计算机搜索,得到8≤χ(KG2(11,5))≤10,10≤χ(KG2(13,6))≤16,其中前一个结论改进了已知的下界7和上界12.

几乎Hamilton连通图和部分平方图(英文)

G为图 ,G 是G的部分平方图 .运用 (k + 2 )连通图 (k≥ 2 )上的插点技术 ,借助LTW序列对G 中独立集的邻域交加权 。

圈平方图复杂性的一个简捷证明

本文给出了圈平方图支撑树数目公式的一个简捷证明。从而也获得它的渐近性质．

哈密尔顿性，邻域并和部分平方图

利用插点方法,研究图的H-性,给出了k-连通图是哈密尔顿的充分条件:设G是k-连通图(k≥2),若对于每个Y∈Ik+1(G*),在G中,有σb(Y)=sum from i=o to k(|N(Yi)|>/(b+k)/2(n(Y)-1)+μ((b(2k-2b+1))/2-1) ,则G是哈密尔顿图.

哈密尔顿性和部分平方图的独立集(英文)

设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-哈密尔顿的或哈密尔顿连k通的统一证明.其充分条件是在图G中关于∑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}|.

2-连通外部平面图的平方图的列表染色

图G的平方图,记作G2,是一个以原图的顶点集作为顶点集,若原图中两点的距离不大于2则连以边所成的图.图G的列表染色数,记作lχ(G),定义为最小的自然数k,使得满足:对任一顶点给定k种颜色的列表,且染色时每个顶点的颜色只能从自身的颜色列表中选择时,总存在G顶点的一个正常染色.设G是一个最大度为Δ(G)的2-连通外部平面图,则lχ(G2)≤Δ(G)+2.

外部平面图的平方图的染色(英文)

图G的平方图 ,记作G2 ,是一个以原图的顶点集为顶点集 ,若原图中两点的距离不大于 2则连以边所成的图 .本文确定了圈的平方图的色数 .对于外部平面图 ,得到以下结论 :设G是一个最大度为Δ(G)的简单连通外部平面图 ,G≠C5.则 χ(G2 )≤Δ(G) +2 .

圈的平方图的Smarandachely邻点全色数

对简单图G(V,E)f,是从V(G)∪E(G)到{1,2,Λ,k}的映射,k是自然数,若f满足(1)u,v∈E(G),u≠,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),\C(u)\C(v)\≥1并且|C(v)\C(u)|≥1;则称f是G的Smarandachely邻点全染色.本文给出了圈的平方图的的Smarandachely邻点全色数.

部分平方图的独立集和1-几乎Hamilton性

借助于部分平方图独立集讨论了图的 1 几乎Hamilton性 ,得到G是 1 几乎Hamilton图的一个充分条件 .

平方图的邻点全和可区别全染色

进一步研究了平方图的邻点全和可区别非正常全染色问题:利用平方图的结构构造了路、圈、毛毛虫、广义星以及最大度为3且不含2度点的树的平方图,通过组合分析法得到上述5类平方图的邻点全和可区别非正常全色数。

若干平方图的均匀全色数

讨论了路,圈,星,扇和轮的平方图的均匀全染色问题,得到了其均匀全色数.

稀疏图平方图的染色数上界

图G的平方^G^2定义为顶点集V(G)=V(^G^2),并且uv∈E(^G^2)当且仅当u和v之间的距离至多为2.^G^2的色数χ(^G^2)是指使得^G^2存在正常k-顶点染色的最小整数k.用权转移的方法证明:如果mad(G)<4且Δ(G)≥7,则χ(^G^2)≤3Δ(G)+1;如果mad(G)≤4且Δ(G)≥8,则χ(^G^2)≤3Δ(G)+5.

几类电力控制数为1的平方图

图G=(V,E)的平方图G2是由G得到的图,G^2的点集是V,G^2中两点相邻当且仅当这两点在图G中距离是1或2.研究平方图的电力控制集问题,给出几类电力控制数为1的平方图.

关于平方图中1-因子的一点注记

本文证明了:设G是p≥4(p为偶数)连通图,若G最多有一个割点,则任意u,v∈V(G^2)(u≠v),G^2-{u,v}有1-因子。

圈平方图的强边染色

圈平方图是在一个圈的基础上连接距离为2的点之后得到的图.为了研究圈平方图的强边色数,将其视为一个哈密顿圈和内圈的并,依次对其进行强边染色,证明了圈平方图的强边色数小于等于14,推广了强边染色的相关结果.

图的哈密顿路骨架上的BB-染色

为了有效解决网络信息传输系统中的频道分配问题,在设计网络线路时,只对该网络线路中更重要的子结构(称为骨架)给出更多的限制,而对其他的部分作较少的限制,这类问题可抽象为图的BB-染色模型,它是经典染色理论的重要变体.利用圈平方图和广义Petersen图描述两类特殊的网络信息传输系统,采用哈密顿路径作为图的骨架,对圈平方图和广义Petersen图的λ-BB-染色展开研究,得到了BBC_(λ)(G,P)=λ+2.

最大度为5的平面图的平方的最小度

设G是一个最小度为5的平面图.证明了δ(G2)≤Δ(G)+17,其中G2、δ(G)和Δ(G)分别记作图G的平方图、最小度和最大度.