一个关于(k;g)-笼的猜想的证明

(k;g) -笼是指具有围长 g的 k-正则图中那些顶点数最小的图 .文 [2 ]中有下面的猜想 :设 G为一个 ( k;g) -笼 ,则它的每一个 g-圈 C是不可分离的 ( nonseparating) ,也就是说 ,对 G中任意的 g-圈 C,G- C仍是连通的 .对于偶数 g,[2 ]已给出了此猜想的证明 .本文中 ,证明 :对于奇数 g,此猜想也是正确的 .     

围长对是(4,5)的最小正则图

我们把围长对是(g,h)的 k-正则图称为(k;g,h)-图;(k;g,h)-图的顶点的最少数目用 f(k;g,h)表示.本文证明了(?)我们还构造了最小(2s+1;4,5)-图,s≥1的无限族.这样,我们就完全解决了 Harary和 Kovács 提出的问题1.     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广,对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λ_h一定存在(1≤h≤n/2)。本文证明了:当d_-正则的n_-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d_-正则的n_-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h:1≤h≤min{g-1,n/2},λ_h达到其最大可能值,即λ_h=hd-2(h-1)。     

可迁图的超常边连通度的最优性

图的超常边连通度是图的边连通度概念的推广.对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λh一定存在(1≤h≤n/2).本文证明了当dr正则的n-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d-正则的n-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h1≤h≤min{g-1,n/2},λh达到其最大可能值,即λh=hd-2(h-1).     

平面图的绑定数

图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数． Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4．设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数．本文,我们证明了如果r4<(5n3)/2 10,则猜想1成立;如果r5<12,则猜 想2成立．     

不含相交6-圈的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色·一个图G称为单射κ-可选择的,如果对于顶点V(G)的任何一个大小为κ的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v)使得G为单射κ-可选择的最小κ,称为G的单射可选择数,记作X_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数X(∑)≥0的曲面∑的一个图,证明了若Δ≥7,g≥6,且不含有相交6-圈,则x_i~l(G)≤Δ+2.     

2—连通正则二部图的长圈

Dirac 定理指出:若 G 是 n 个顶点的2-连通图,(?){d(x)}≥k,则 G 有长至少为 min(2k,n)的圈(见[1]).‖本文把 Dirac 定理应用到2-连通正则二部图,得到如下的结果:定理1 设 G 是2-连通 k-正则二部图,G 的顶点数为 n,则 G 有长至少为 min(4k,n)的圈(k≥2).‖     

环面图上的一个Lebesgue型定理及其在线性染色中的应用

设c是图G的一个顶点染色, 如果c的任意两个色类都导出一个最大度至多为2的无圈子图,则称c为G的一个无圈染色. 我们首先证明了环面图上的一个Lebesgue 型定理, 作为其应用证明了对任一个围长不小于5 的环面图G, 除非△(G) = 4 而且G有一个子图H使得H的每一个面都是与三个3度点和二个4度点相关的5度面, H一定是(「(△(G))/2」+ 4)- 线性列表可染色的. 这一结果推广和改进了一些已知结论.     

正则多部竞赛图中任意弧的所有长度的外路

多部竞赛图D中弧x_1x_2的一条(l-1)一外路是指起始于x_1x_2的长为l-1的路x_1x_2…x_1,其中要么x_1与x_1同部,要么x_1控制x_1.特别地,当l=|V(D)|且x_1控制x_1时,x_1x_2…x_lx_1是一个通过弧x_1x_2的Hamilton.Guo(Discrete Appl.Math.95(1999)273-277)证明了一个正则c-部(c≥3)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,c}.作为一个推广,该文证明了一个正则c-部(c≥5)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,|V(D)|}.进一步,使用路收缩技巧,下面一个结果也被证明:D是一个正则c-部(c≥8)竞赛图,且每个部集包含两个顶点,则D的每条弧被包含在一个Hamilton圈中.这个结果部分地支持了Volkmann和Yeo(Discrete Math.281(2004)267-276)提出的猜想:正则多部竞赛图的每条孤都包含在一个Hamilton圈中.     

关于图是(g,f,n)-临界图的充分条件

设G是一个图. 设g和f是两个定义在V(G)上的整值函数使得对V(G)所有的顶点x有g(x)f(x). 图G被称为(g,f,n)-临界图,如果删去G的任意n个顶点后的子图都含有G的(g,f)-因子. 本文给出了图是(a,b,n)-临界图几个充分条件. 进一步指出这些条件是最佳的. 例如,如果对V(G)所有的顶点x和y都有g(x)＜f(x), n+g(x)dG(x)和g(x)/(dG(x)-n)f(y)/dG(y),则G是(g,f,n)-临界图.