6连通图中的可收缩边

Kriesell(2001年)猜想：如果κ连通图中任意两个相邻顶点的度的和至少是2[5κ/4]-1则图中有κ-可收缩边．本文证明每一个收缩临界6连通图中有两个相邻的度为6的顶点，由此推出该猜想对κ=6成立。     

随机图的广义3-连通度

图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广.     

2-控制数和连通2-控制数相等的图(英文)

任意一个图G =(V ,E) ,S是V(G)的子集 ,如果对每一个顶点u∈V-S都存在顶点v∈S ,使得d(u ,v) ≤ 2 ,则称S为G的一个 2 控制 .称最小的 2 控制集的顶点个数为G的 2 控制数 ,记为γ2 (G) .如果G的一个 2 控制集S的生成子集〈S〉是一个连通图 ,则称S为G的一个连通 2 控制集 .称最小的连通 2 控制集的顶点个数为G的连通 2 控制数 ,记为γc2 (G) .本文论述了树和单圈图中 2 控制数和连通 2 控制数相等的充分必要条件 .     

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,     

周长为3的m限制边割连通图

如果连通图的G存在边割S,使得G-S的每一个连通分支都含有至少m个顶点,则称图G是m限制边连通的.本文刻画了周长为3的m限制边连通图.     

临界h-边-连通图的临界度

图G称为k-临界h-边-连通的,若h=λ(G)且对每个k顶点集{u1,…,uk}有λ(G-{u1,…,ui})≤λ(G-{u1,…,ui-1})-1,I≤k.若G是k-临界h-边-连通但不(k 1)-临界h-边-连通,则记之为(h*,k*)λ.本文证明了:存在(h*,k*)λ图的充要条件是(1)1≤k≤[(h 1)/2],h≡0,1,2(mod 4);1≤k≤[(h-1)/2],h≡3(mod 4);或(2)k=h,G=Kk 1.     

关于图是(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)-临界图.     

不含相交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.     

K1,p-受限图

图G中同构于Ki,p的子图叫G的p-爪(P≥3)．如果G中任意一个p-爪中1度顶点之间边(在G中的边)的数目≥P-2,则称G为K1,p-受限图,它是无爪图的推广．本文证明了连通、局部2-连通的K1,4-受限图是完全圈可扩的．     

笛卡尔乘积图的圈点连通度

图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}.     

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

两类网络的2-限制连通度

给定图G=(V,E)和非负整数h,图G的h-限制点割S是V(G)的一个子集(如果存在)使得G-S不连通且G-S中任一点的度数至少为h.图G的h-限制连通度κ~h(G)是G的最小h-限制点割的阶数.本文中,我们证明了κ~2(FCQ_n)=4n-4 (n≥8),κ~2(SQn)=4n-8(n≥4),其中FCQ_n和SQ_n分别是n维折叠交叉超立方体和n维spined cube.     

连通的欧拉生成子图

本文证明了：若G是一个p顶点的、2－边－连通简单图，其边数，q≥(p-4↑ 2) 7，则除K2，5外，G有连通的欧拉生成子图。当q=(p-r↑ 2）＋6和κ′（G）＝2时，本文给出了全部6个极图。     

关于Sumner-Blitch猜想的一个注记

设G是一个图。G的最小度，连通度，控制数，独立控制数和独立数分别用δ，k，γ，i和α表示，图G是3－γ-临界的，如果γ=3，而且G增加任一条边所得的图的控制数为2.Sumner和Blitch猜想：任意连通的3－γ临界图满足i=3，本文证明了如果G是使α＝k 1≤δ的连通3－γ-临界图，那么Sumner-Blitch猜想成立。     

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

K1,4-受限图的路可扩性

图G中同构于K1,p的子图叫G的p-爪(p3).如果G中任意一个p-爪中1度顶点之间边的数目p-2,则称G为K1,p-受限图,它是无爪图(p=3时)的推广.本文证明了:连通、局部3-连通的K1,4-受限图是路可扩的.     

临界2-棱-连通图

§1.引言 以G=(X,E)表示有限阶的简单图,其中X是G的顶点集,E是G的棱集。若x∈X,我们以G—x表示从G中删去x及与它相关联的棱所得到的图。其它未加说明的术语及记号,均见于[1]。 设G是2-棱-连通图,x是G的一个顶点。若G—x不是2-棱-连通的,则称x关于图G的2-棱-连通性是临界的,或简称x是G的一个临界点;反之,若G—x也是2-棱-连通的,则称x是G的非临界点。每一个顶点都是临界点的2-棱-连通图,称为临界2-棱-     

平面图的绑定数

图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成立．     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

关于拟k-连通图的一个注释

G是一个k-连通图,T是G的一个k-点割,若G-T可被划分成两个子图G1,G2,且|G1 |≥2,|G2 |≥2,则称T是G的一个非平凡点割.假定G是一个不含非平凡(k-1)点割的(k-1)-连通图,则称G是一个拟k-连通图.证明了对任意一个k≥5且t＞k/2的整数,若G是一个不含(K2+tK1)的k-连通图,且G中任...