关于2-边连通3正则图荫度的一个注（英文）

图G的点荫度a(G)是G的使得每个子集诱导一个森林的顶点划分中子集的最少个数.我们熟知对任何平面图G,a(G)≤3,且对任何直径最大是2的平面图有a(G)≤2.文献[European J.Combin.,2008,29(4):1064-1075]中给出下列猜想:任何没有3-圈的平面图都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.本文证明了任何2-边连通上可嵌入的3-正则图G(G≠K_4)都有一个顶点的划分(V_1,V_2)使得V_1是独立集,V_2诱导一个森林.     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

几类新的上可嵌入图

讨论了几类上可嵌入的边连通简单图,得到了如下结果:若G为简单连通图,且满足以下条件1)-3)之一:1)G为1-边连通的,且不含完全图K_3,α(G)≤3,2)G为2-边连通的,且不含完全图K_3,α(G)≤5,3)G为3-边连通的,且不含完全图K_3,α(G)≤10,则G是上可嵌入的,且在上述相应条件下,独立数上界都分别是最好的.     

不含三角形的图的λ3-最优性的充分条件

设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.     

3-边可染的3-正则图（英文）

若一个连通图的每条边都包含在某一完美匹配中,则称之为匹配覆盖图.设G是一个3-连通图,若去掉G的任意两个顶点后得到的子图仍有完美匹配,则称G是一个brick.而brick的重要性在于它是匹配覆盖图的组成结构因子.3-边可染3-正则5的刻画问题是一个NP-完全问题.本文将此问题规约到3-正则匹配覆盖图上,进而规约到其组成结构因子brick上.我们证明了:一个3-正则图是3-边可染的当且仅当它的所有brick是3-边可染的.     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

局部连通图的群Z_3-连通性

本文研究了局部连通图的群连通性的问题.利用不断收缩非平凡Z_3-连通子图的方法,在G是3-边连通且局部连通的无爪无沙漏图的情况下,获得了G不是群Z_3-连通的当且仅当G是K_4或W_5.推广了当G是2-边连通且局部3-边连通时,G是群Z_3-连通的这个结果.     

1-平面图及其子类的染色

如果图G可以嵌入在平面上,使得每条边最多被交叉1次,则称其为1-可平面图,该平面嵌入称为1-平面图.由于1-平面图G中的交叉点是图G的某两条边交叉产生的,故图G中的每个交叉点c都可以与图G中的四个顶点(即产生c的两条交叉边所关联的四个顶点)所构成的点集建立对应关系,称这个对应关系为θ.对于1-平面图G中任何两个不同的交叉点c_1与c_2(如果存在的话),如果|θ(c_1)∩θ(c_2)|≤1,则称图G是NIC-平面图;如果|θ(c_1)∩θ(c_2)|=0,即θ(c_1)∩θ(c_2)=?,则称图G是IC-平面图.如果图G可以嵌入在平面上,使得其所有顶点都分布在图G的外部面上,并且每条边最多被交叉一次,则称图G为外1-可平面图.满足上述条件的外1-可平面图的平面嵌入称为外1-平面图.现主要介绍关于以上四类图在染色方面的结果.     

3限制边连通度与正则因子

设G是一个阶不小于6的k正则连通点可迁图. 如果G不含三角形, 那么图G是极大3限制边连通的, 或者G含有各连通分支都同构于同一个h阶点可迁图的k-1正则因子, 其中2k-2≤h≤3k-5. 唯一的例外是: G是围长等于4 的3正则图.     

图的上可嵌入性与圈中顶点度

本文利用非上可嵌入图的充要条件,结合圈中顶点最大度与图的上可嵌入性之间的关系,得到了下两个结果:(1)设G是2-边连通简单图,若对G中任意圈G,存在点x∈C满足,d(x)>|V(G)|/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.(2)设G={x,y;E}为简单二都图,且是2-边连通的. |x|=m,|Y|=n(m,n≥3),若对G中任意圈C,存在点x∈C且x∈X满足d(x)>n/3 1,则图G是上可嵌入的,且不等式的下界是不可达的.     

Klein瓶上的6-正则嵌入图的着色性质

Brooks证明了:若G是连通的简单图,并且它既不是奇圈,又不是完全图,那么它的色数至多为△(G),其中△(G)为图G的最大度.它可以推出嵌入到Klein瓶上的任意的一个6-正则图的色数至多为6.通过对Klein瓶上的6-正则嵌入图的结构分析,证明了Klein瓶上的任意的一个6-正则嵌入图的色数为5.     

点可迁图中的正则因子

设图G是一个K-正则连通点可迁图.如果G不是极大限制性边连通的,那么G含有一个(k-1)-因子,它的所有分支都同构于同一个阶价于k和2k-3之间的点可迁图.此结果在某种程度上加强了Watkins的相应命题:如果k正则点可迁图G不是k连通的,那么G有一个因子,它的每一个分支都同构于同一个点可迁图.     

几类特殊θ-图的Laplacian谱唯一性问题研究

通过θ-图中除了含有一个4圈的θ-图外,其余的θ-图都是邻接谱唯一图的有关结论,研究了几类特殊θ-图的Laplacian谱唯一性问题.即:θ-图θ_(s_1,s_2,s_3)(|s_i-s_j|≤2,1≤i≤3)、圈长为3或4的θ-图以及θ-图θ_0,u,v(u+v=1(mod 2)).     

围长为3的点可迁图的3限制边连通度

设G是阶至少为6的k正则连通图.如果G的围长等于3,那么它的3限制边连通度 λ3(G)≤3k-6.当G是3或者4正则连通点可迁图时等号成立,除非G是4正则图并且 λ3(G)=4.进一步,λ3(G)=4的充分必要条件是图G含有子图K4.     

图的上可嵌入性与围长及相邻顶点度和

$G$是一个阶为$n$围长为$g$的简单图, $u$和$v$是$G$中任意两个相邻顶点, 如果$d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 5$, 则$G$是上可嵌入的; 如果$G$是2-\!边连通(或3-\!边连通)图, 则当 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g + 3$ (或 $d_{G}(u)$ + $d_{G}(v)$ $\geq$ $n - 2g - 5$)时$G$是上可嵌入的, 并且上面3个下界都是紧的.     

n 阶临界3-边连通图的最大边数

本文中未经说明的术语和记号采自[2].设 G=(V,E)是一个简单图。G 的顶点数记作 n(G),边数记作 m(G),即 n(G)=|V|,m(G)=|E|.假设 G 是3-边连通图.G 的顶点 v(?)V 称为 G 的临界点,如果 G-v 不是3-边连通的;否则称为 G 的非临界点.如果每个 v(?)V 都是 G 临界点,则称 G 是临界3-边连通图.临界3-边连通图类记作 A,A_n 是 A 中所有 n 阶图的集合.假设 G(?)A,则对每个 v∈A,     

关于图的余树的奇连通分支数的内插定理

本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T) 1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.     

路的字典积的邻和可区别边染色

图G的正常[k]-边染色σ是指颜色集合为[k]={1,2,...,k}的G的一个正常边染色.用w_σ(χ)表示顶点χ关联边的颜色之和,即■,并称w_σ(x)为x关于σ的权.图G的k-邻和可区别边染色是指相邻顶点具有不同权的正常[k]-边染色,最小的k值称为G的邻和可区别边色数,记为x′_Σ(G).现得到了路P_n与简单连通图H的字典积P_n[H]的邻和可区别边色数的精确值,其中H分别为正则第一类图、路、完全图的补图.     

p阶临界2-边连通图的最大边数

设G=(V,E)是2-边连通图,若对每个点v∈V,G-v不是2-边连通图,则称G是临界2-边连通图. 本文证明了p阶临界2-边连通图的最大边数是 7, P=6; (1/8)(P~2+4p) p=0(mod 4); f(p)= (1/8)(P~2+2p+13) p=1(mod 4); (1/8)(P~2+28) p=(2mod 4),p≠6 (1/8)(P~2+2p+9) p=3(mod 4)。并且给出了达到最大边数的极值图.     

折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.