正则图联图的Ihara zeta函数及其应用

图G的Ihara zeta函数是一个一元函数.首先用代数方法得到了两个正则图联图的Ihara zeta函数的一个因子乘积表达式,在此基础上得到了正则图联图的3种基尔霍夫指标(基尔霍夫指标、度和基尔霍夫指标和度乘基尔霍夫指标)之间的一个关系式.     

顶点距离大于2的局部化条件与hamiltonian图

对任意正整数i,若图G的导出子图L的顶点满足x,y∈V(L), dL(x,y)=imax{dG(x),dG(y)}≥|G|/2,则称L具有性质DL(i).设C(G)为图G的闭包,本文证明了下述结果任意一个C(G)=G且边连通度≥3的2-连通图,若存在正整数s使得G中的导出子图L满足(i) L(≌)K1.3有性质DL(2);(ii) 任意正整数i,1≤i≤s,L(≌)Bi有性质DL(i);(iii) L(≌)Z s+2有性质DL(s+2),则G为hamiltonian图.由此得到每个边连通度≥3的2-连通{K1.3;Bi,1≤i≤s}-free图, 若C(G)＝G且max{dG(x),dG(y) 对任意导出子图L(≌)Zs+2 ,dL(x,y)=s+2}≥|G|/2,则G一定是hamiltonian图.从而Fan条件中顶点距离可扩展为s+2.     

拟二面体群的一个无限类1-正则4度Cayley图

群G的一个Cayley图X=Cay(G,S)称为正规的,如果右乘变换群R(G)在Aut(X)中正规.得到了拟二面体群G＝〈x,y|x2m=y2=1,xy=xm 1〉(其中m=2s,s为大于4的偶数)的一个无限类4度正规1-正则Cayley图 Cay(G,S),其中S={x,x-1,xs 1y,xs-1y},并且对2r阶拟二面体群的正规1-正则4度Cayley图进行了分类,其中r＞3.证明了2r阶拟二面体群的任意4度正规1-正则Cayley图同构于Cay(G,{x,x-1,xs 1y,xs-1y}),其中s=2r-2.     

Halin图的L(d,l)标号

给定图G和正整数d,图G的L(d,1)标号是指从图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有|f(x)-f(y)|≥d;当dG(x,y)=2时,有|f(x)-f(y)|≥1。图G的L(d,1)标号数λd(G)是指最小的正整数k使得G有一个L(d,1)标号f满足f(V){0,1,2,…,k}。已知对于最大度为Δ的一般图有λd(G)≤Δ2 (d-1)Δ。讨论了Halin图的L(d,1)标号问题,证明了λd(G)≤Δ 3(2d-1)。     

图的L(p,q)-标号问题

令G为图,p,q为2个正整数,p≥q。G的一个L(p,q)-标号是映射f:V(G)→{0,1,2,…},使得对任意x,y∈V(G),若dG(x,y)=1则|f(x)-f(y)|≥p;若dG(x,y)=2则|f(x)-f(y)|≥q。G的一个m-L(p,q)-标号是标号f:V(G)→{0,1,2,…},使得对任意x∈V(G),有f(x)≤m。并称λp,q(G)=min{m|存在G的一个m-L(p,q)-标号}为图G的L(p,q)-数。本文给出k-退化图、G1和G2的联图G1∨G2及G1和G2的M-matched sum图G1M G2的L(p,q)-数不同上界。最后给出仙人掌图,唯一圈图L(p,1)-数λp,1(G)的可达界。     

图的周长

设G为n阶2连通图,D(x)={y|y∈V(G)~\(x),d(x,y)≤2},δ_o=min{max{d(x),d(y)}|x,y∈V(G),d(x,y)=2},D(δ_o)={x|x∈V(G),d(x)≥δ_o},δ~*为G中的顶点度且满足:(Ⅰ)δ~*尽可能的大,(Ⅱ)对经(?)x∈D(δ_o)及D~*(x)={y|y∈(D(x)∪{x}),d(y)<δ~*}有|D~*(x)|相似文献   

双圈图的剖分的有关结果

图G的剖分是指把图G剖分成一些只含孤立点或孤立边的分支,它是有序整数对(x,y),用符号D(G)表示。本文介绍了有关双圈图剖分的一些简单结果。     

关于图的圈的一个充分条件

设G为n(≥3)阶2连通图,δ≤δ~*≤Δ,对任意x∈V(G),记D(x)={y|y∈V(G)\{x},d(x,y)≤2},D~*(x)={y|y∈(D(x)∪{x}),d(y)<δ~*},本文证明:如果|D~*(x)|相似文献   

哈密尔顿图的一类新的局部化充分条件

设L为图G的一个导出子图 ,若有 x ,y∈V(L) ,只要dL(x ,y) =2就有max{dG(x) ,dG(y) }≥ |G| / 2 ,则称L有局部Fan性质 .该文证明了以下结果 .G是一个 2_连通的 {K1.3 ,B1} -free图 .对任意一个整数s≥ 0 ,若G的任一个导出子图L∈ {Bi,0≤i≤s;Zs+2 }均有局部Fan性质 ,则G是Hamiltonian图 ,除非s=2且G H9.由此得到每个 2_连通的 {K1.3 ,Bi,0≤i≤s;Zs+2 }_free图除s =2且该图同构于H9外 ,均为Hamiltonian图 .     

正则图的Q-图的(度)基尔霍夫指标

由图G的Q-图的电阻距离和(乘法度或加法度)基尔霍夫指标的定义,讨论了图G的Q-图的(乘法度或加法度)基尔霍夫指标与图G的线图的基尔霍夫指标的关系,并给出了相应的例子。