具有次大Wiener指数的单圈图

设G=(V,E)是一个简单连通图,V和E分别为G的顶点集和边集.研究了单圈图的Wiener指数,利用单圈图的Wiener指数的计算公式,刻划了具有次大Wiener指数的单圈图的特征.     

树图的外围维纳指标的下界

设G=(V,E)为简单连通图.对v∈V(G),顶点v的离心率ε(v)=max{d(u,v)│u∈V(G)}, d(u,v)为图G中顶点u,v间的距离.图G的直径为d(G)=max{ε(v)│v∈V(G)}.外围顶点集P(G)指图G中满足ε(v)=d(G)的所有v=V(G).图G的外围维纳指标为■.首先讨论了当树图T的外围顶点个数确定时,它的第二下界;然后讨论了当树图T的顶点数目确定时,其对应的PW(T)的最小值,及达到其最小值的极图.     

直径不超过4的树的零阶广义Randi(c)指数

图G=(V,E)为简单连通图,dv表示顶点v的度.G的零阶广义Randi(c)指数定义为R0α(G)=∑v∈Vdαv,其中α为任意实数.本文研究直径不超过4的树关于零阶广义Randi (c)指数的极图问题.     

图的corona积的局部反魔幻着色数

令G=(V(G),E(G))是具有n个顶点、m条边的连通简单图.称一个双射f:E(G)→{1,2,…,|E(G)|}为图G的一个局部反魔幻标号,如果f满足对于G中任意两个相邻的顶点u和v都有w(u)≠w(v),其中w(u)=∑e∈E(u)f(e),E(u)是与点u相关联的边的集合.若对图G的顶点v着颜色w(v),则图G...     

两类树图的Hamiltonian色数

一个n阶连通图G的Hamiltonian染色是从G的顶点集V(G)到正整数集N(称为颜色集)的一个映射c,使得对于G的任意2个不同的顶点u和v满足|c(u)-c(v)|+D(u,v)≥n-1,其中D(u,v)表示G中u到v的最长路径的长度。对一个Hamiltonian染色c,将max{c(u):u∈V(G)}称为c的值,记作hc(c)。将min{hc(c):c是G的任意Hamiltonian染色}称为G的Hamiltonian色数,记作hc(G)。本次研究得到了满足max{D(u,v)|u,v∈V(G),u≠v}≤n/2的d-重似星树和广义双星这两类树图的Hamiltonian色数的确切值。     

轮,扇,星和双星的邻点扩展和可区别全染色

设G为简单图. G的全k-染色是指k种颜色对图G的全体顶点及边的一个分配.设c是图G的一个全k-染色,任意的x∈V(G),称w(x)=Σx∈ec(e)+Σy∈N(x)c(y)为点x的扩展和,其中N(x)={y∈V(G)|xy∈E(G)}.称图G的全k-染色c为邻点扩展和可区别(简记为NESD),如果w(x)≠w(y),其中xy∈E(G).图G的NESD全k-染色的最小值k被称为图G的邻点扩展和可区别全色数,简记为egndi∑(G).本文探讨了轮,扇,星和双星的邻点扩展和可区别全染色,并得到了它们的邻点扩展和可区别全色数.     

关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.     

具有极值广义连通指数的似星树

设T是一棵似星树,即其中仅有一个顶点的度数大于2的树,并设其中最大的顶点度数为m,T的广义连通指数为R_a(t)∑uv∈E(T),其中d(u)为树T中顶点u的度,α是任意实数.通过图的变换,证明了似星树的广义连通指数Rα(T)是e1m(T)的递减函数,e1m(T)是T中连接一个1度顶点与m度顶点的边数;并由此刻画了具有最大、最小广义连通指数的似星树.     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

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

设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为平衡特征．主要研究一类单圈图的平衡性并给出相应的平衡标号及其特征．     

Mycielski’s图的Co-PI指标

令G是一个图,u是图G的一个顶点, TG（ u）是图G当中除了u以外的其余顶点到点u的距离之和, T（ u）＝TG（ u）＝∑u∈V dG（u,v）,Co-PI指标定义为：Co -PIv（G）＝∑uv∈E（G） T（ u）-T（ v）。文章给出了一些Mycielski’ s图的Co-PI指标的计算公式。     

关于P_(2r,2s-1)的k-优美标号

对于简单图G=,如果存在一个映射f:V(G)→{0,1,2,…,|E|+k-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(u)|u∈V}=|E|+k-1;3)对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),且{g(e1)|e∈E}={k,k+1,…,|E|+k-1},g(e2)=|f(u)-f(v)|,e=uv,则称G是k-优美图,f称为G的k-优美标号.作者研究了一类图的k-优美标号.     

几类特殊图的条件色数

对整数k>0,r>0,图G的条件(k,r) 染色是一个从顶点集V(G)到数集{1,2,…,k}的映射c,使得：（1）相邻点获得的颜色不同;（2）|c(N(v))|≥min{|N(v)|,r}。G的条件色数是使得G有一个正常的(k,r) 染色的最小k值,记为χ_r(G)。本文主要研究了r取3时,几类特殊图的条件色数。     

伞状树的奇强协调性

设G=V,E是一个简单图,若存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足(1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);(2)对任意的e1,e2∈E,若e1≠e2则g(e1)≠g(e2),此处g(e)=f(u)+f(v),e=uv,且{g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇强协调图,f为G的奇强协调标号,讨论了一类树的奇强协调性.     

时变网络中零等待时间最短路问题的一个对偶算法

时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点t,图G中的每条弧(i,j)∈A都附有两个参数:弧的传送时间b(i,j,u)和弧的传送费用c(i,j,u),它们都是在弧的顶点i上的出发时间u的函数.找出从源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.假设除源点外,在其它任何顶点都不能等待,b(i,j,u)是满足u b(i,j,u)≥0( (i,j)∈A,u=0,1,…,T)的任意整数,c(i,j,u)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.     

两种运算下图的Szeged指标和修正Szeged指标的计算

图G的Szeged指标Sz(G)和修正的Szeged指标Sz*(G)分别定义为Sz(G)=Σuv∈E(G)nunv和Sz*(G)=Σuv∈E(G)(nu+n0/2)(nv+n0/2).这里,对于边uv,n0是指图中到u和v距离相等的点数,nu是指图中距u比距v近的点数,nv类似定义.本文给出了强正则图的联图和合成图的Szeged指标和修正Szeged指标的计算公式.     

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

直径为4的奇优美树

对于简单图G=, 如果存在一个映射f: V→{0,1,2,...,2E|-1}满足:对任意的u,v∈V,若u≠v,则f(u)≠f(v);max{f(v)|v∈V}=2|E|-1;对任意的e1,e2∈E,若e1≠e2,则g(e1)≠g(e2),此处g(e)=|f(u)-f(v)|,e=uv;{g(e)|e∈E}={1,3,5, ...,2|E|-1},则称G为奇优美图,f 称为G的奇优美标号.提出一个猜想:每棵树都是奇优美的,文章证明了直径为4的树都是奇优美的.     

长圈的邻域并条件的推广

本文证明了若G为一个k(k≥2)连通简单图,最小度为,δV(G)=n≥3,X 1,X 2,……,X k是顶点集合V的子集,X=X1∪X2∪…∪Xk,且对于Xi(i=1,2……k)中任意两个不相邻点u,v,都有N(u)∪N(v)≥n-δ,则X在G中可圈。并给出几个相关推论.     

无K4-子式图的2-距离和可区别边染色

图G的一个正常边染色φ若满足:∠u,v∈V(G),且d_G(u,v)≤2都有f(u)≠f(v),其中f(u)=∑_uw∈E(G)φ(uw),则称φ为图G的2-距离和可区别边染色。运用反证法,结合构造染色函数法,研究了无K₄-子式图的2-距离和可区别边染色,确定了无K₄-子式图的2-距离和可区别边色数的一个上界。