3连通图的可去边数

设 e是 3连通图 G的一条边 ,如果 G- e是某个 3连通图的剖分 ,则称 e是 G的可去边 .本文给出了 3连通图的可去边数依赖于极大半轮的下界以及达到下界的极图 .     

Slater猜想的证明

本文完全证明了Slater猜想:当2k>n时,完全图K_n+1是唯一的k临界n连通图。     

极小拟(k+1)连通图的最小度

给出了极小拟5连通图有围长大于或等于4的极小拟（k）＋1连通图的最小度。     

团复形是无圈的平面图是可伸缩图

许宝刚猜想:若图G的团复形是无圈的,则G为可伸缩图．本文证明了该猜想对平面图成立,即:若G是团复形为无圈的平面图,则G为可伸缩图．     

k连通图可缩边导出子图的连通性

引进S1 3边形的概念 .证明了 ,对于k(k =3或 4)连通图G ,若G无S1 3边形 ,则 是 2连通的 ;另外也得到 ,设G是k(k≥ 2 )连通图 ,若对G的任一断片F ,有｜F｜ >[k/2 ]+ 1 ,则 是 2连通的 .从而改进并推广了N .Dean的结论 .     

临界2棱连通图的最大度及度大于4的顶点数的上界

1、前言对一些特殊图类的最小度,人们已经有了较多的认识,然而对于图的最大度及其它度的顶点的性质所知还不多。对临界2棱连通图,当其2度顶点数给定时,我们给出最大度的上界(定理1)及度大于4的各类顶点数的上界(定理2、3),并且这些上界都是最好可能的。我们讨论的都是有限阶的简单图,不另加说明的术语和记号与Bolloás同。     

粘合运算对图的控制参数的影响

简单图G的粘合运算G_(uv)指的是重合G的两个顶点{u,v}并且去掉重边和环所得到简单图的运算．本文考虑了粘合运算对图的4个控制参数γ(G),Γ(G),β(G),i(G)的影响．刻画了图G_(uv)与图G的控制参数γ(G),Γ(G),γ(G),i(G)之间的关系．及给出γ(G_(uv))=γ(G)-1和β(G_(uv)=β(G)-1的充要条件．     

3连通平面图的可去边数

设e是3连通图G的一边。如果G-e是某个3连通图的剖分,则称e是G的可去边。用v表示G的顶点数,本文证明了当v≥6时,3连通平面图G的可去边数的下界是v+4/2,此下界是可以达到的。     

阶较小时具有最大棱数的极小k棱连通图

设 G 是极小 k 棱连通图,|G|=n.Mader 已证明,当 k≥2,n≥3k 时,e(G)≤k(n-k),且 e(G)=k(n-k)的充要条件为 G=K~(k,(n-k)).当 k≥2,k+2≤n<3k时,我们得到 e(G)≤(n+k)~2/8,并给出 e(G)=(n+k)~2/8时图的结构.就其作用来说,本文所获得的结果与蔡茂诚关于极小 k 连通图的结果相似.     

临界n-棱-连通图的最小度

A graph G is said to be Critically n-line-connected if it is n-line-connected. but for each x∈G, λ (G - x )≤n- 1 .The following result is proved; Every critically n-line-connected graph contains at least two vertices of degree n, and then this lower bound is best possible as n≥ 3 .