有r(≥3)个圈仙人掌图的零阶广义Randic指数的界

设G为一简单连通图,则G的零阶广义Randic指数定义为R0α(G)=∑v∈V(G)dα(v),其中d(v)为顶点v的度数,α为非0和1的实数;图G称之为仙人掌图,如果G的每一块要么是一条边,要么是一个圈.此文主要研究有r(≥3)个圈仙人掌图的零阶广义Randic指数的界.     

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.     

关于图的两个化学指标

设G是简单图,对G中任意顶点v,dv表示点v的度数.图G的Randic指数,也称为图G的连通性指数,定义为R=R(G)=∑uv∈E1dudv.图G的ABC指数定义为ABC(G)=uv∑∈E(G)du+duddvv-2.Ballobas等人于1998年证明了"在没有孤立点的图中,星图的Randic指数最小",Pavlovic等人于2001年用另一种方法也证明了此结论.该文得到了这个结论更加简单的证明方法并给出了六角链ABC指数的极值.     

给定悬挂点的三圈图的零阶广义Randic指数

对于简单的连通图G,它的零阶广义Randic指数0Rα(G)定义为Σv∈V(G)[dG(v)]α,其中α是一个给定的实数,dG(v)是G中顶点v的度.简单连通图G的零阶广义Randic指数是化学图论中一个重要的拓扑指数,其在化学领域中有着广泛的研究及应用.基于此对于任意的α(≠0,1),它给出了顶点个数为n,悬挂点为k的所有三圈图的零阶广义Randic指数0Rα的一些紧的界.     

具有极值Randic’指标的二树图研究

简单连通图的Randic’指数是化学图论中一个重要的拓扑指数,其在化学领域中有着广泛的研究及应用.我们给出了一个具有n个顶点的二树图的最大和最小的Randic’指数,即2n-4/2(n-1)+1/n-1≤R(G)≤n/2-11/4+23/3+6/3+2/2同时当二树图达到这两个界限时,它的图也被刻画了出来.     

图的Laplacian谱半径界的可达性

设G为n阶连通的简单图 ,ρ(G)为图G的邻接谱半径 ,μ(G)表示G的Laplacian谱半径。(d1,d2 ,… ,dn) (其中d1≥d2 ≥…≥dn)为G的顶点度序列 ,令r=max{d(u) +d(v) ｜ (u ,v) ∈E(G) } =d(x) +d(y) ,s=max{d(u) +d(v)｜ (u ,v) ∈E(G) - (x ,y) }。该文证明了μ(G)上下界的可达性 :μ(G) =μ≤ 2 + ρ(LG) ,等式成立当且仅当G是偶图。μ(G)≤ 2 + (r- 2 ) (s- 2 ) ,成立等式当且仅当G为半正则偶图或P4 。μ(G)≥d1+ 1,成立等式当且仅当d1=n- 1。     

关于冠图的关联着色

设 G =( V,E)是一个图 ,称 I( G) ={ ( v,e) |v∈ V,e∈ E,v与 e相关联 }是 G的关联集 .I( G)的两元素 ( v,e)和 ( w,f )是相邻的当且仅当下列三条之一成立 :( 1) v=w;( 2 ) e=f ;( 3) vw =e或 f .图 G的关联着色是从 E( G)到一颜色集 C的映射 ,使得 E( G)中任何两相邻元素有不同的像 ,其中 C中所含元素的最小个数称为 G的关联色数 ,记为 inc( G) .这一概念是 Brualdi等在 1993年提出的 ,并提出了如下猜想 :每个图都能用Δ ( G) +2种颜色进行关联着色 .本文证明了对于树图、轮图、扇图、圈和完全二部图的冠图猜想成立 .     

关于S.Win的一个猜想

令G是一个图,P=|V(G)|,(?)u,v∈V(G),uv(?)E(G),d(u)+d(v)≥P+K,其中k是整数,则称G为Ore k—型图。S.Win提出如下猜想:若G是2n(n≥1)阶Ore k—型图(-1≤k≤2n-4),则G具有k+2个边不重的1—因子。本文证明了k=-1时,Win猜想成立。实际上,除个别图处,我们证明了更强的结论:若G是2n(n≥2)阶Ore-1—型图,且G(?)H_i(i=1,2),则G具有两个边不重的1—因子。     

变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

有圈二部图覆盖的一个结果

H.Wang猜想,对于任意整数k≥2,存在N(k)使得二部图G=(V1,V2,E)中,V1=V2=n≥N(k),且对于G中任意一对不相邻的顶点x∈V1,y∈V2,有d(x)+d(y)≥n+k,那么,对于G中任意k个独立边e1,e2,e3,…,ek,存在顶点不重的k个圈C1,C2,…,Ck,使得ei∈E(Ci),i∈{1,2,…,k}和V(C1∪C2∪…∪Ck)=V(G).H.Wang及J.A.Bondy对k=2,3时证明了猜想成立,本文对k=4证明了猜想的正确性.     

关于图的距离控制数的上界

对于任意的正整数l,连通图G的顶点子集D被称为距离l 控制集 ,是指对于任意顶点v D ,D中至少含有一个顶点u ,使得距离dG(u ,v) ≤l.图G距离l 控制数γl(G)是指G中所有距离l 控制集的基数的最小者 .确定图G的距离l 控制数γl(G)是NP 问题 .给出了当G是阶数为p (p ≥l 1 )的连通图时 ,对于任意的正整数l,都有最优上界γl(G)≤ p-Δ l - 1 l .而且针对某些Δ和l,是对Meir和Moon的结果的一种改进     

顶点最大度被限制的图的边转发指数

对于给定的n阶连通图G,一个路由选择R是指G中的n(n-1)条路集,其中每个有序点对都有路集中的一条路连接.图G关于R的边转发指数π(G,R)是R中路经过一条边的最大条数.图G的边转发指数π(G)是G关于任何路由选择R的边转发指数π(G,R)的最小值.符号πΔ,n表示所有顶点数为n,最大度至多为△的图中最小边转发指数.当n≥4p 1,且n()[4p [1/3(2p-1)]-1,6p]时,其中p≥1,确定了πn-2p,n的值.     

正则图的代数连通度

设G=(V,E)是一个具有n个顶点的简单图,A(G)是G的邻接矩阵,D(G)表示G的度对角矩阵,图G的拉普拉斯矩阵定义为L(G)=D(G)-A(G).若矩阵L(G)的特征值为μ1≥μ2≥…≥μn-1≥μn=0,则称μn-1为G的代数连通度.研究了正则图的代数连通度,得到了下列结论:μn-1≤(nrln(n-l))/(6n-8-4r-nln(n-1))这里,r表示正则图的度.     

图的谱半径和泛圈性

设G=(V,E)是一个n阶m条边的简单连通图,μ(G)为图的邻接矩阵的最大特征值。本文利用图的谱条件讨论了图的泛圈性,证明了n(n≥5)阶图G,如果μ(G)n-2,则G是泛圈图除非G=Kn-1+e。     

树图的全控制数

设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中叶子的数目。     

关于图C_m∪P_(n-1)~+的优美性

图Ｃｍ ∪Ｐ＋ｎ－ １ 是圈Ｃｍ 与Ｐ＋ｎ－ １ 的不交并。本文证明了当①ｍ ＝ ４ｋ,ｎ ≥ｋ ＋ ２;②ｍ ＝ ４ｋ ＋ １,４ｋ － １ ≤ｎ ≤１０ｋ－ ７;③ｍ ＝ ４ｋ＋ ２,ｎ ≥４ｋ ＋ １;④ｍ ＝ ４ｋ ＋ ３,４ｋ＋ ２≤ｎ ≤１０ｋ－ ２ 时,图Ｃｍ ∪Ｐ＋ｎ－ １ 是优美的。     

关于在K1,n-free图中存在正则因子度条件的推广

图被称为K1,n-free图,如果它不含有导出子图K1,n。设G是一个具有顶点集V(G)的图,并设g和f是两个定义在V(G)的函数,使得g(x) f(x)对所有V(G)中的点x都成立。设a=max{g(x)|x∈V(G)},b=min{f(x)|x∈V(G)},并有b,a 2,n b/(a-1) 1(如果存在点v∈V(G)使得f(v)≡1(mod2),假定b n-1)。证明了:每个连通的使得∑x∈V(G)f(x)为偶数的K1,n-free图G有(g,f)-因子,如果它的最小度至少是(n-1)(a 1)b 1「b a(n-1)2(n-1) -n-1b「b a(n-1)2(n-1) 2 n-3.这个结果是K.Ota和T.Tokuda(J.GraphTheory.1996,22:59-64.)关于在K1,n-free图中存在正则因子度条件的推广。     

图的子图中(n,r)-正交因子分解

设图G的顶点集为V(G)，边集为E(G)，g和f是定义在V(G)上的2个整值函数，满足对于一切x∈V(G)，g(x)≤f(x).若G是一个(mg+rn，mf-rn)-图，1≤n＜m，r≥2，且对于x∈V(G)，有g(x)≥k≥1，则存在G的一个子图G′，使得G′具有一个(f，g)-因子(n，r)-正交于G的任意给定子图H，其中｜E(H)｜=nk.     

关于图的点着色的一个猜想的探讨

Lovasz 在 1968 年提出了猜想[1]:若 G 不是完全图,并且x=m+n-1,这里 m≥2 以及n≥2,则存在 G 的不相交子图 G1和G2使得X(G1)=m 和 X(G2)=n.该文举例说明该猜想并不一定成立,同时给出使此猜想成立的一些充分性条件.