临界 h 棱连通图的最大棱数及其极值图

对于给定的正整数 p 和 h,p≥h+1且 h≥4,本文给出了 p 阶临界 h棱连通图的最大棱数并且确定了所有达到最大棱数的 p 阶临界 h 棱连通图.     

复合图及其连通度和临界度

本文确定了H(G)的点-连通度及H(G)关于点-连通度的临界度;确确定了H(G)的边-连通度及某种H(G)关于边-连通度的临界度。     

临界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.     

收缩临界5-连通图的平均度

M．Kriesell证明了收缩临界5-连通图的平均度不超过24并猜想收缩临界5-连通图的平均度小于10．本文构造了一个反例证明M．Kriesell的猜想不成立并给出了收缩临界5-连通图平均度新的上界．     

临界图的星色数

1988年,Vince定义了图的色数的一个推广——图的星色数,本文研究了有围长限制或有最大度限制的临界图的星色数,得到了三个新结果。     

色临界图的最大度与色数的一个关系式

研究了一类简单图G的色数x(G)与最大度△(G)的关系,对满足x(G)>(S~2+S)/2的X(G)+S阶色临界图G,证明了x(G)=△(G)+1-S,或等价地,△(G)+1-[((8△(G)+17~(1/2)-3/2]≤X(G)≤△(G)+1,这一结果部分改进了Brooks经典不等式X(G)≤△(G)+1,并完全刻画n+3(n≥4)个顶点的n-临界图的结构。     

h连通图中非临界点的个数

设Ｇ是ｈ连通的简单非完全图，ｖ中Ｇ的顶点，若ｋ（Ｇ－ｖ）≥ｋ（Ｇ），则称ｖ是Ｇ的非临界点，关于Ｇ中非临界点的个数，Ｖｅｌｄｍａｎ和苏健基分别给定了在不同条件下的下界，本文推广了他们的结果，得到了更一般的下界。     

临界κ连通图中的点度数

如果在—个κ连通图G中删掉任意一个顶点后得到的图都不再是κ连通,则称G为临界κ连通.Chartrand,Kaugars和Lick证明了每一个临界κ连通图(κ≥2)都含有一个度数小于(3κ-1)/2的顶点.Hamidoune进一步证明了每一个临界k连通图都至少含有两个这样的顶点,并且这一下界是最优的.在本文中,我们证明如果一个临界κ连通图恰好含有两个度数小于(3κ-1)/2的顶点,则这两个顶点的度数一定是κ.     

关于临界h棱连通图的最大棱数及最大图的结构(Ⅰ)——每点都与h度点相邻的最大临界h棱连通或h连通图的结构

图G称为临界h棱连通(或h连通)的,如果G是h棱连通(或h连通)的,但对每个x∈V(G),G-x不再是h棱连通(或h连通)的。对h≥4,本文确定了每点都与h度点相邻的所有具有最大棱数的临界h棱连通(或h连通)图的结构。     

一个图的匹配数条件

设G是一个简单图,在图G中任意一个最大匹配的基数叫做G的匹配数,记作v(G),在这篇文章中我们获得了下面的结果,(1)设G是连通的和不完全的,则对于x,y∈v(G)和xyE(G),v(G-{x,y}=v(G)-1的充分必要条件是(a)G[A(G)]是完全的和A(G)的每一个点和C(G)的每一个点相邻,(b)c(D(G))=|A(G)| 1,和(c)y∈D(G-x)对于x,y∈C(G)。(2)设G是连通的和不完全的,则v(G-{x,y})=v(G)-2对于x,y∈V(G)和xyE(G)的充分必要条件是GK_(n,n),其中n≥2。     

图的连通控制数与无赘数的一个不等式

设G是连通图,γ_C(G)和ir(G)分别表示G的连通控制数和无赘数。孙良于1990年证明了γ_c(G)≤4ir(G)—2,同时提出猜想γ_c(G)≤3ir(G)—2。本文进一步研究γ_c(G)与ir(G)的关系,并证得上述猜想成立。     

收缩临界6连通图的6度顶点

利用断片的性质,改进了齐恩凤,齐登记等的研究结果,得到了收缩临界6-连通图中6度点的性质的新结果:设x是G中任意一点,设A是一个x-原子,记N_A=T_A,N(x)∩T_A≠Φ,则A∩T_A中有与x相邻的6度点或两点的距离为2.     

临界图的边数

本文研究了△－临界图的边数下界，其中△＝１０，１１，１２，１３。     

6连通图中的可收缩边

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

短圈并图的列表极值数(英文)

The list extremM number,f(G) is defined for a graph G as the smallest integer k such that the join of G with a stable set of size k is not |V(G)|-choosable.In this paper,we find the exact value of f (G),where G is the union ofedge-disjoint cycles of length three,four,five and six.Our results confirm two conjectures posed by S.Gravier,F.Matfray and B.Mohar.     

具有｜V（G）｜＋2个最大匹配的因子临界图G^＊

在连通图G中,如果对任意的V∈V(G),G-v有完美匹配,则称G是因子临界图.该文刻画了具有|V(G)| +2个最大匹配的因子临界图.进而,刻画了一些特殊的双因子临界图.     

3连通图的可去边数

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

关于（ξ,k）—临界图

设G为连通图,且ξ（G）=k≥1,若对G中任意边e,均有ξ（G\e）=k-1,则称G为(ξ,k)-临界图。本文刻划了ξ-1-临界图的若干性质,给出了一个图为ξ-1-临界图的一些充分或必要条件,以及一些ξ-1-临界图类。     

边覆盖临界图的一些性质

设G是一个简单图,其顶点集为V(G)而边集为E(G),S∈E(G)称为 G的一个覆盖,如果由S导出的子图为G的一个生成子图. G的边覆盖色数χ'c(G)是E(G,)所能划分成的最大边覆盖数.已知δ-1 ≤χ'c(G)≤δ,由此将χ'c(G)=δ的图称为CI类图,否则称为CII类图.若G是连通CII类图,且G不是完全图,对任意的u,u∈V(G),e=uv( )E(G),都有χ'c(G+e)＞χ'c(G)成立,则称G为边覆盖临界的.本文研究了边覆盖临界图的一些性质.即若G为边覆盖临界图,则对任意的u,v∈V(G),若e=uv( )E(G),总存在w∈{u,v},有d(w)≤2δ-2,且w至少与max{d(w)-δ+1,3d(w)-4δ+4}个最小度顶点相邻.