复合毛毛虫树的优美及奇优美性

对于一棵n阶树T,如果存在一个映射f:V(T)→{0,1,2,…,n-1},对不同的顶点x,y∈V(T),有f(x)≠f(y),且边标号集合{f′(uv)|uv∈E(T)}={1,2,…,n-1},其中f′(uv)=|f(u)-f(v)|,称T为优美树,并称f为T的一个优美标号.利用优美树的定义和性质证明复合毛毛虫树的优美性和奇优美性.     

极大局部边连通有向图的度条件

对有向图D=(V(D),E(D)),顶点u和v的局部边连通度λ(u,v)=min {X:X∈E(D),D-X中不存在从u到v的路}.若对D中任意两个顶点u和v,λ(u,v)=nin{d+(u),d-(v)},称D为极大局部边连通的.笔者得到了有向图是极大局部边连通的两个度条件.推广了别人的三个结果.     

限制弧连通有向图的充分条件

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件.     

蕴含强(p,q)哈密尔顿性的几个条件

利用路收缩技术,证明了,如果有向图D满足下列条件中的任何一个,(1)最小半度δ0(D)≥(n+p+q)/2;(2)D是(p+q+1)强连通有向图,且d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,这里,x,y是任意控制顶点对,u,v是任意被控制顶点对;(3)D的弧数超过(n-1)2+q2+p;那么D是强(p,q)哈密尔顿的.     

两类并图的优美标号

讨论2n个优美二分图与一条通路并的优美性,得到如下结论:设二分图G=(X,Y,E)优美,优美标号为θ,边数为q,a=max{k|0相似文献   

优美树问题简介

§1.引言设N_n={1,2,…,n},T是有n-1条边的树(n≥2)。所谓T的一个优美值θ是指由T的顶点集V到N_n的一个双射(即由V到N_n的一个一一映射),使l(uv)=|θ(u)-θ(v)|是T的边集E到N_(n-1)的一个双射,这里uv表示联结顶点u和v的边。若树T有一个优美值,则说树T是优美的(参看图1)。在一般情况下,当T是一个有n-1条边的简单图,θ是由V到N_n的一个子集的双射,且l(u,v)满足上述条件,则这图就叫优美图(参看图2)。     

K1×mCn的k-边优美指标集

设G=(V,E)是一个p点q边图.对于非负整数k,若存在双射f:E→{k,k+1,…,k+q-1},使得其导出映射f+:V→Zp,f+(u)≡∑(u,v)∈Ef(u,v)modp也是一个双射,则称此图G是k-边优美的.称EGI(G)={k:G是k-边优美的}是G的边优美指标集.在此彻底解决了图K1×mCn(mn≡0mod 2)的边优美指标集.     

蒲公英图T_m~r的k-边优美指标集

设G=(V,E)是一个p点q边图.对于非负整数k,若存在双射f:E→{k,k+1,…,k+q-1},使得其导出映射f+:V→Zp,f+(u)≡∑(u,v)∈Ef(u,v)mod p也是一个双射,则称此图G是k-边优美的.称GEI(G)={k:G是k-边优美的}是G的边优美指标集.完全确定了蒲公英图Trm(m>0,r≥0)的边优美指标集.     

关于Scrambling指数的最新研究结果

设 n,q,s是正整数, 满足1≤s相似文献   

网格图的2-彩虹控制数

给定一个图G和正整数k,图的彩虹控制函数f是满足下列条件的映射f:V(G)→2{1,2,…,k},使得对某个顶点v满足f(v)=,则∪u∈N(v)f(u)={1,2,…,k},其中V(G)是图G的顶点集,N(v)表示所有与v相邻的顶点的集合.彩虹控制函数f的权定义为w(f)=∑v∈V(G)|f(v)|.图的k-彩虹控制数γrk(G)是所有彩虹控制函数的权中的最小权.研究了2-彩虹控制函数的启发式算法的网格图的构造方法,实验结果表明,基于禁忌搜索策略的模拟退火算法比传统的模拟退火算法具有较好的效果.     

图∪ni=1mi∧j=1A(nj)的优美性

n(n≥2)条长为2的路具有两个共同的端点的二分图记为A(n)=(X,Y,E),其中X为2n度顶点集合,y为2度顶点集合,记X={u1,u2},y={v0,v1,…,vn-1｝,A(nj)=(Xj,Yj,Ej)(nj≥2)中的Xj={v1j,v2j},Yj={v1j,v2j,…,vnjj-1｝(j=1,2,…,m),用一条边连接vnjj-1与u2j+1(j=1,2,…,m-1)得到的图记为∧mj=1A(nj).图∪ni=1∧mij=1A(nj)是n个∧mij=1A(nj)的不交并,本文证明了∪ni=1∧mij=1A(nj)是优美的且是交错的.     

C_m·P_n的D(3)-点可区别边色数

对阶数不小于3 的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,...,α},若{u,v}∈V(G),1≤d(u,v)≤β,有C(u)≠C(v) 则称f为G的一个α -D(β)-点可区别的边染色,简记为α -D(β)-VDPEC,对一个图进行α -D(β)-点可区别的边染色,所需的最小的α称为图G的D(β)-点可区别的边色数,记为χ′β-vd(G),其中d(u,v)表示两个点之间的最短距离.得到Cm·Pn的D(3)-点可区别边色数.     

一类有向图的星边弧染色

提出了有向图的星边弧染色的概念,并定义了有向图D的星边弧色数,记为(→x)s′(D).运用Lovász局部引理证明了若有向图D=(V,A)的最大出度△+与最大入度A-满足线性关系△+=k△-(△(D)≥7,k＞0),则(→x)s′(D)≤16[(√1+k2)/1+k△3/2]*,这里[*]*表示上取整.     

一类超欧拉有向图中的超欧拉bypass

设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass.     

两类树图的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色数的确切值。     

一类新图的奇优美性的研究

设L为简单无向图G的一个顶点标号,L称为图G的奇优美标号,若L满足以下两条:(1)L为G的顶点集V到{0,1,…,2 ︱E︱-1}的一个单射;(2)由L′(e)=︳L(u)-L(v)︳(其中e=uv)决定的边标号L′是从G的边集E到{1,3,…,2 ︱E︱-1}的一个双射.本文给出了一类特殊简单图G*的奇优美标号,并给出了相应的标号算法及相关的一些证明.     

Banach空间分数阶微分方程边值问题解的存在性与唯一性

应用单调迭代技巧研究了抽象的Banach空间E中一类非线性分数阶微分方程边值问题{-D——0~α+u(t)=f(t,u(t)),t∈I,u(0)=u′(0)=u′(1)=θ解的存在性,其中2α≤3是实数,I=[0,1],Dα0+是标准的Riemann-Liouville导数,f:I×E→E连续,θ为E中的零元.在较弱的单调性条件和非紧性测度条件下,通过构造上下解的单调迭代过程,获得该边值问题最小、最大解对的存在性及解的存在唯一性.     

有向图是极大连通的和超连通的充分条件（英文）

设D是顶点集为V(D)的有限简单有向图.V(D)中的顶点v的度d(v)被定义为v的出度d+(v)和入度d-(v)中的最小值.如果有向图D的最小度为δ,连通度为κ,则κ≤δ.如果κ=δ,则称有向图是极大连通的.对极大连通的有向图D的每个最小点割S,如果D-S要么是非强连通的且至少有一个平凡的强连通分支,要么是平凡的,则称D是超连通的.通过弧数给出有向图或二部有向图在最小度给定时是极大连通的或超连通的充分条件,并举例说明这些条件中的下界是紧的.     

边色数为Δ的一个充分条件

设Δ(G)=max{d(v)|v∈V(G)},其中d(v)为顶点v的度数,χ′(G)为图G的边色数,对于简单图G,χ′(G)=Δ,或χ′(G)=Δ+1[1].满足χ′(G)=Δ的图称为第一类图,而满足χ′(G)=Δ+1的图称为第二类图.目前虽已弄清了某些图的类别,但给出第一类图与第二类图的特征仍是一个尚未解决的困难问题[1][2][3].设S={v|v∈V(G),d(v)=Δ},本文证明了当|S|=1或2时,简单图G是第一类图,即χ′(G)=Δ.以下讨论的图均指简单图.现将有关定义和结论叙述如下,其它定义和符号按[1].定义1　对图G的边着色F,若与顶点v关联的某些边染有颜色i,则称颜色i在顶点v上表现…     

关于有向图的强弧连通度

在图论中,图的连通性研究是一个较重要的方面,因为图的许多性质都与图的连通性有着密切的联系.李慰萱在其所著的《图论》一书中介绍了有向图的各种连通度,并且给出了有关强弧连通度λ_3与最小出入度δ_3的两个结论1.对任何有向图D,K_3≤λ_3≤δ_3.2.若D是一个强有向图,δ_3≥[p/2],则λ_3=δ_3.我们推广了上述第2个结论,得到了下面的结果:定理 若D是一个有P个顶点的有向图,记d_3(v)=min{odv,idv},如果存在整数k(1≤k≤4),使对D中任意k个顶点v_1,…,v_k都有d_3(v_1)+…+d_3(v_k)≥k/2(p-2)+1/2则λ_3=δ_3.