关于(ξ,1)-临界图与上可嵌入性

设G为连通图,且ξ(G)=k≥1,若对G中任意边e,有ξ(G\e)=k-1,则称G为(ξ,k)-临界图.利用ξ-1-临界图的上可嵌入性,通过研究ξ-1-临界图的加重边、点扩张、圈扩张的ξ-1-临界性,得到了新的上可嵌入图,从而丰富了上可嵌入图的种类和求法.     

3-边连通图的Betti亏数与奇度点

图G是3-边连通的且G的奇度点的数目为k.若k小于等于4,则G是上可嵌入的; 若k大于等于6,则ξ(G)小于等于k/2减去1.而且当k不小于6时,存在无限多个3边连通图G使得ξ(G)等于k/2减去1.     

极小四阶限制边连通图

设G是有限简单无向图,k是正整数.使G-S每个分支的阶不小于k的边割S称为G的k阶限制边割.G的四阶限制边连通度λ4(G)是G的四阶限制边割之中最少的边数.若对于任意边e∈E(G),均有λ4(G-e)=λ4(G)-1,则称G是极小四阶限制边连通图.定义ξ4(G)=min {(e)(U):U(∪)V(G),G[U]是四阶连通导出子图},此处(e)(U)表示恰好有一个点在U上的边的数目.若λ4(G)=ξ4(G),则称G是λ4最优的.若每个5阶限制边割都孤立出G的一个5阶连通子图,则称G是超级5阶边连通的.笔者给出:极小四阶限制边连通图若不是λ4最优的,则是3正则,围长为5,任意边都关联5圈,且是超级5阶边连通的图.     

最大次数为3的色指数临界图的一种构造

G的k-(边)着色是一个映射π:E(G)→{1,2,…,k},使得G的相邻边没有相同的象.图G的色指数x'(G)=min{k| G有一个k-着色}.给出了最大次数为3的图的5种类型的四边形扩张变换,证明了这5种类型的变换保持图的临界性不变,并可利用这种变换构造出阶数较高的新的临界图.     

二部图λ_3最优性的一个原子条件

设G=(V,E)是有限简单无向图,U是G的一个边割,k是一正整数.若G-U的每个分支的阶至少为k,则称U为G的一个k阶限制边割.定义G的k阶限制边连通度λk(G)为G的k阶限制边割中最少的边数,达到最小的称为λk割.定义ξk(G)=min{(F):F是G的k阶连通子图},其中(F)表示恰好有一个端点在F上的边的数目.如果λk(G)=ξk(G),则称G是λk最优图.本文给出了二部图λ3最优性的一个原子条件.     

边连通简单图的独立数与上可嵌入性

文章讨论了边连通简单图的独立数与上可嵌入性的关系,得到了下列结果:(1)设G是一个k-边连通简 单图(k=1,2),若α(G)≤k,则G是上可嵌入的;(2)设G是一个3-边连通简单图,若α(G)≤5,则G是上可嵌入 的。     

图的反符号边全K-控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1}如果∑e′∈N(e)f(e′)≤0对于至少k条边e∈E成立,则称f为图G的一个反符号边全k控制函数。一个图G的反符号边全k控制数定义为γkst(G)=max{∑e∈Ef(e)|f为图G的反符边全k控制函数}。本文主要给出了连通图G的反符号边全k控制数γkst(G)的若干上限。     

边连通简单图的独立数与上可嵌入性

文章讨论了边连通简单图的独立数与上可嵌入性的关系，得到了下列结果：(1)设G是一个k-边连通简单图(I=1，2)，若口(G)≤k，则G是上可嵌入的；(2)设G是一个3-边连通简单图，若口(G)≤5，则G是上可嵌入的。     

直径为2与3的符号图的上可嵌入

设Σ=(G,σ)是直径为2和3连通的简单符号图,G是Σ的基础图.若Σ扭转等价Δ_2-图或Δ_3-图,则Σ的Betti亏数ξ(Σ)=2,否则Σ是上可嵌入的,即ξ(Σ)≤1.     

图是λ3-最优和超级-λ3的范型条件

设G是有限简单无向图,使G-S的每个分支都包含至少k个点的边割S称为G的k-限制边割。G的k-限制边连通度λk(G)是G的k-限制边割之中最少的边数。定义ξk(G)=min{[U,U-]:U V(G),|U|=k,G[U]是连通的},若λk(G)=ξk(G),则称G是λk-最优的。若任意最小k-限制边割都孤立一个k阶分支,则称图G是超级-λk的。应用范型条件给出了图是λ3-最优和超级-λ3的充分条件。     

k阶限制边连通度最优的一个充分条件

设S是图G的一个边子集,若G-S不连通且每个分支的阶至少为k,则称S为G的一个k-限制边割.若G有k-限制连割,G的最小k-限制边割的边数称为G的k阶限制边连通度,记为λk(G).记ξk(G)=min{|[X,]|∶|X|=k,G|X|连通},若λk(G)=ξk(G),则称G是λK-最优的.证明了若对G中任意一对不相邻的顶点x,y都有d(x) d(y)≥n 2(k-2),且G不是G*k图,则G是λk-最优的.     

3正则3连通图的转发指数

n阶连通图G的路由选择R是由连接G的每个有向顶点对的n(n-1)条路组成.R经过G的每个顶点(每条边)的路的最大条数称为G关于R的点转发指数ξ(G,R)(边转发指数π(G,R)).对G的所有路由选择R,ξ(G,R)(π(G,R))的最小值称为G的点转发指数ξ(G)(边转发指数π(G)).对于k正则k连通图G, Fernandez de la Vega和Manoussakis [Discrete Applied Mathematics, 1989, 23(2):103-123]证明ξ(G)≤(n-1)·[(n-k-1)/k]和π(G)≤n[(n-k-1)/k],并且猜想ξ(G)≤[(n-k)(n-k-1)/k].我们分别改进了ξ(G)≤(n-1)[(n-k-1)/k]-(n-k-1)和π(G)≤n[(n-k-1)/k]-(n-k),并且证明了猜想对k=3的情形.     

扇形图与匹配图的临界星图Ramsey数

对于完全图Kn和一个额外的顶点v,通过在v与Kn之间添加k条边所得出的图,记为KnK1,k.设G和H是任意的图,临界星图Ramsey数r*(G,H)定义为最小的正整数k,使得图KN-1K1,k的任意红蓝2-边着色,或者存在单色的红色子图G,或者存在单色的蓝色子图H,这里N指的是Ramsey数r(G,H).文中找到了r(Fn,mK2)的所有临界图,利用这些临界图得到了临界星图Ramsey数r*(Fn,mK2)=m+1,nm≥1,以及r*(Fn,mK2)=2 m,n≤m,这里Fn=K1+nK2是扇形图.     

图的边覆盖数、围长和最大亏格

设G为图,用ω(G)和g(G)分别表示图G的边覆盖数和围长.结合图G的边覆盖数和围长等条件,得到了Betti亏数ξ(G)的一个上界,即设G为k-边连通图,则ξ(G)≤{|V(G)|-ω(G)(「)g(G)/2」, k=1,max{1,|V(G)|-ω(G)(k-1)(「)g(G)/2」-1},k=2,3.进而得到最大亏格γM(G)的一个下界.所得结果改进了目前已有的结果.     

边色数的点与边临界性质

关于边色数的点与边临界我们得到如下结论: 定理1 设图G是边色数边临界的。d(v)=2。N(v)={u,w}。且(u,w)∈E(G)。令G′=G·v,若x是G′中分离u,w之割点,则必存在y∈V(G′),使得(x,y)∈E(G′)且d(x)=d(y)=△(G)。定理2 若图G是边色数边临界的,且边集{e,f}为G的二边割,又设e=(x,y),f=(u,w)则二边割e,f边分别关联G的最大次顶点。     

图到其二次迭线图内的关联嵌入

图G到图H的子图上的同构称为G到H内的嵌入。本文给出图到其2次迭线图内一种特殊嵌入——关联嵌入的分类,证明每个可关联嵌入到共2次迭线图内的连通图,都能夠由一个称为胚的可嵌入子图通过一系列扩张得到,而图的胚依据形状可分为四种类型:H_k(k≥0),C_n(n≥3),A_k(k≥-2,k≠0)和B_k(k≥-3)。此外,本文还研究了关联嵌入的计数与共轭性。     

图是极大3限制边联通的充分条件

设S是连通图G中的一个边子集。若G S不连通且它的每个连通分支的阶至少为k,则称S是G的一个k限制边割。图G的最小k限制边割的边数称为G的k限制边连通度,记为λκ(G)。定义ξκ(G)=min{|［X,X］|:|X|=k,G［X］连通},其中X=V(G)＼X。若λk (G)=ξk(G),则称G是极大k限制边连通的。设G是一个围长至少为5的λ3 连通图。本文证明了若G中不存在5个点u1,u2,v1,v2,v3使得d(ui,vj)≥3(i=1,2;j=1,2,3),则G是极大3限制边连通的。     

Cartesian积图的边泛圈性

网络中子图的可嵌入性是度量网络优劣的一个重要性能。圈作为网络拓扑中一类重要的子图,其可嵌入性可以通过泛圈性来度量。Cartesian积图是互联网络拓扑结构中一类非常重要的图类。设G是长为k1和k2的圈的Cartesian积图。利用Cartesian积图的顶点和边的传递性,证明了当k1≥3,k2≥3,G是边偶泛圈的;当k1,k2均为奇数时,G是（k1＋k22）-边泛圈的。     

关于临界图性质的一个结论

图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的色数.1965年,Vizing证明了任意最大度是Δ的图的边色数或者是Δ或者是Δ 1.若为前者,则称图是第一类的,否则称为第二类的.若G为连通的第二类图,且对G的任意边e,有χ′(G-e)<χ′(G),则称图G为Δ临界图.对于临界图的性质的研究有助于对图的分类问题的研究.本文给出了如下定理:G是一个Δ临界图,x是G中的一个Δ点,如果|N4(x)|=3,那么对u∈N4(x),N≤Δ-1(u)=φ.     

超限制边连通笛卡尔乘积图的边容错性(英文)

如果G-F不连通且每个连通分支至少含有两个顶点,则连通图G的边子集F称为限制边割.如果图G的每个最小限制边割都孤立G中的一条边,则称G是超限制边连通的(简称超λ′).对于满足|F|≤m的任意子集FE(G),超λ′图G的边容错性ρ′(G)是使得G-F仍是超λ′的最大整数m.这里给出了min{k1+k2-1,υ1k2-2k1-2k2+1,υ2k1-2k1-2k2+1}≤ρ′(G1×G2)≤k1+k2-1,其中,对每个i∈{1,2},Gi是阶为υi的ki正则ki边连通图且ki≥4,G1×G2是G1和G2的笛卡尔乘积.并给出了使得ρ′(G1×G2)=k1+k2-1的一些充分条件.