完美整数k-匹配和k-因子临界图

本文研究完美整数k-匹配和k-因子临界图的存在性.扩张常数表示图的连通强度,对于正则图,利用扩张常数给出了完美整数k-匹配存在的一个充分条件,这推广了Hamers等人和Cioabǎ等人的结果.此外,对于正则图,基于扩张常数还给出了k-因子临界图存在的一个充分条件.

孤立韧度变量和分数(k,n)-临界图

孤立韧度变量I′(G)是衡量网络健壮性的有效工具,定义|S|和i(G-S)-1的最小比值,其中S■V(G)满足i(G-S)>1。图G称为分数(k,n)-临界图,若从G中删除任意n个顶点,其剩余子图依然存在分数k-因子。文献[10]中得到分数k-因子存在性的紧I′(G)界。论文将文献[10]的结果推广到分数临界图,即:若δ(G)≥k+n且I′(G)>2k+n-1,则G是分数(k,n)-临界图,其中k≥2和n≥0是整数。

分数临界图的新韧度条件（英文）

一个图G称为分数(g,f,n)-临界图如果满足从G中删除任意n个顶点,其剩余子图依然存在分数(g,f)-因子.得到分数(g,f,n)-临界图的新韧度条件,若t(G)≥b2-1-Δ+bn/a,则G是分数(g,f,n)-临界图,其中Δ=b-a.进一步地,给出分数(a,b,n)-临界图的韧度条件.

极大非独立集可削去的因子临界图(英文)

如果对一个简单图G的每一个与G的顶点数同奇偶的独立集1,都有G-I有完美匹配,则称G是独立集可削去的因子临界图.如果图G不是独立集可削去的因子临界图,而对任意两个不相邻的顶点x与y,G+zy是独立集可削去的因子临界图,则称G是极大非独赢集可削去的因子临界图.本文刻画了极大非独立集可削去的因子临界图.

控制圆点临界图的若干性质

对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图.

弱控制参数的去边临界图研究

图的束缚数是图的控制数研究中的一个重要方面,它在某种程度上反映了图的控制数对边数的敏感度,而去边临界图在图的束缚数研究中又极其重要.本文主要研究图的弱控制参数的去边正临界图(γw+-ER-critical)和去边负临界图(γw--ER-critical),并分别给出了二次图为去边正临界图和去边负临界图的充要条件.

具有|V(G)|+2个最大匹配的因子临界图G

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

(a,b,k)-临界图(英)

设G是一个图且设a，b是非负整数，a＜b．如果消去G的任意K个顶点剩下的图有[a，b]-因子，则称图G是（a，b，k）-临界图，本文给出了一个图是（a，b，k）-临界图的一个充分必要条件，讨论了该条件的一些应用，研究了（a，b，k）-临界图的性质。

边色临界图的1-因子和几乎1-因子的存在性

根据Vizing邻接引理和关于临界图的独立数的一个结论,利用图的1-因子和几乎1-因子存在的充要条件,采用结构图论的方法证明了:1)若G是2n阶Δ-临界图,且Δ≥n,δ≥n-2,则G存在1-因子;2)若G是2n+1阶Δ-临界图,且Δ≥n+1,δ≥n-2,则G存在几乎1-因子.

临界图独立数的上界

1968年,Vizing猜想,对于n阶的Δ临界图G,其独立数α(G)≤2n.利用著名的Vizing邻接引理和Fiorini不等式的证明方法,证明了如果临界图G的一个最大独立集中主顶点个数不超过1,则猜想成立,从而改进了Luo等的一个结果.

关于临界图的若干结果

Ｖｉｚｉｎｇ’ｓ猜想：ｎ阶Δ＿临界图的边数ｍ满足ｍ≥（ｎΔ－ｎ＋３）／２．本文证明了当ｎΔ＝３时猜想也成立以及当５≤Δ＜ｎ２，ｎΔ＝４时猜想也成立．

边覆盖临界图的一些性质

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

临界图的边数

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

关于直径为2-临界图的Murty-Simon猜想

称图G是直径为2-临界图,如果G的直径是2,任意删掉一条边这个图的直径都会增加。一个非常著名的猜想,称为Murty-Simon猜想,指出对于任意有n个点的直径为2-临界图,它的边数最多为[n^(2)/4],且为完全二部图K_([n/2],[n/2])时可以取到边数的上界。一个图称为是3_(t)-临界图,简记为3_(t)EC,如果它的全控制数是3,并且任意加一条边全控制数都会减少。利用直径为2-临界图和全控制边临界图之间的关系,要证明Murty-Simon猜想只需要证明n个点的3_(t)EC图,它的边数大于[n(n-2)/4]。设δ(G)和α(G)分别表示G的最小度和独立数。最后,得到了3_(t)EC图G一定满足α(G)≤δ(G)+2。并且,对于满足α(G)=δ(G)+2的3_(t)EC图G,猜想一定是成立的。

关于临界图性质的一个结论

图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的色数.1965年,Vizing证明了任意最大度是Δ的图的边色数或者是Δ或者是Δ+1.若为前者,则称图是第一类的,否则称为第二类的.若G为连通的第二类图,且对G的任意边e,有χ′(G-e)<χ′(G),则称图G为Δ临界图.对于临界图的性质的研究有助于对图的分类问题的研究.本文给出了如下定理:G是一个Δ临界图,x是G中的一个Δ点,如果|N4(x)|=3,那么对u∈N4(x),N≤Δ-1(u)=φ.

量利式盈亏临界图在利润敏感性分析中的应用

从分析盈亏临界图的基本形式的缺陷入手，提出采用量利式盈亏临界图（又称利润图）来进行目标利润敏感性分析；并辅以数学公式的推导，佐证利润图可形象、直观地反映各因素的变化对目标利润的影响程度。

孤立韧度与分数(a,b;n)-临界图

设G是一个图,a,b,n是正整数且1 a b,n 0.定义了分数(a,b;n)-临界图,并给出了G是分数(a,b;n)-临界图的与孤立韧度有关的充分条件.

关于9-临界图边数的下界

本文给出了9-临界图边数的下界:m≥118/39 n,其中n为点数,m为边数。

边临界图的新下界

图G为简单的第二类连通图,且对G的任意边e,有x′(G-e)<x′(G),则称G是临界的.该文给出了阶为n边数为m的Δ-临界图的新下界,即m≥(3Δ+6)n/10,这里12≤Δ≤18.

一类边覆盖临界图的构造

在图的边覆盖染色中边覆盖临界图的构造问题一直是研究的热点和难题.给出了一类边覆盖临界图的构造方法.对于任意给定的最小度δ,利用该方法可以构造出相应的一类边覆盖临界图.