连通简单MCD图边数的一个新的下界

设Ｇ是具有ｎ个顶点的２－连通简单ＭＣＤ图，ｆ２（ｎ）表示Ｇ的边数．本文证明了当ｎ≥８时，其中ｘｍ＝ｕｍ－２ｕｍ－５，ｕｍ是Ｆｉｂｏｎａｃｃｉ数．     

28个顶点的简单MCD图

设Ｓｎ是ｎ个顶点的没有等长圈的简单图的集合．若Ｇ∈Ｓｎ且Ｓｎ中不存在图Ｇ＇使｜Ｅ（Ｇ＇）｜＞｜Ｅ（Ｇ）｜，则称图Ｇ是简单ＭＣＤ图．若简单ＭＣＤ图Ｇ是２连通的，则称Ｇ是２连通简单ＭＣＤ图．本文证明了不存在具有２８个顶点的含有同胚于Ｋ４的子图的２连通简单ＭＣＤ图．于是结合ＤｉｓｃｒｅｔｅＭａｔｈ．１２６（１９９４），我们完全证明了下述定理：存在ｎ个顶点的含有同胚于Ｋ４的子图的２连通简单ＭＣＤ图当且仅当ｎ∈｛１０，１１，１４，１５，１６，２１，２２｝．     

2－连通简单MCD图边数的一个新的下界

设Ｇ是具有ｎ个顶点的２－连通简单ＭＣＤ图，ｆ２（ｎ）表示Ｇ的边数．本文证明了当ｎ≥８时，其中ｘｍ＝ｕｍ－２ｕｍ－５，ｕｍ是Ｆｉｂｏｎａｃｃｉ数．     

关于非广义多边形路的2连通简单MCD图

令Sn是具有n个顶点没有两个等长圈的简单图的集合,若Sn中不存在图G′使│E（G′）│＞│E（G）│,则称图G是简单MCD图,若简单MCD图G是2连通的,则称G是2连通简单MCD图,若G中一条路P的两个内点u都有dG(v)=2,则称P为G的简单路,一个2连通可平面图G称为广义多边形路,如果用下述方法得到图G是路,对应于G的每个内部面f(G-是G的平图）有一个G＊的顶点f*,G*的两个顶点f*和g*,在G＊中相邻当且仅当G－中相应的两个内部面的边界交于一条G－的简单路,作者证明了下述结果,当且仅当n∈{10,11,14,15,16,21,22}时,存在n个顶点的非广义多边形路的2连通简单MCD图。     

至多有2个等长圈的简单图的最大边数

设Sn是具有n个顶点至多有2个等长圈的简单图的集合。若Sn中不存在图G’使|E(C’)|>|E(G)|,Ng称G是简单的最大图分布(2)图(简记为简单MCD(2)图)。用f~*(n,2)表示具有n个顶点的简单MCD(2)图的边数。作者证明了f~*(n,2)≥(n-l)+[1/2(11n-20)~(1/2)]且当3≤n≤10时等式成立。     

各等长圈数不超过2的简单图的最大边数

设Sn是具有n个顶点各等长圈数不超过2的简单图的集合．若Sa中不存在图G＇使｜E（G＇）｜〉｜E（G）｜,则称G是简单的最大圈分布（2）图（简记为简单MCD（2）图）．用f＊（n,2）表示具有n个顶点的简单MCD（2）图的边数．证明了对每个整数11≤n≤14,有f＊（n,2）=n＋[1/2（√11n-20 -2）],其中[a]是小于等于a的最大整数。     

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

本文给出了9－临界图边数的下界：m≥118／39n,其中n为点九，m为边数。     

至多有2个等长圈的简单图的最大边数

分f*（n,2）表示具有n个顶点的至多有2个等长国的简单图的最大边数．证明了当n≥15时,f*（n,2）≥n＋2Zk－4＋［」,其中k＝［（16＋／42）．     

8—临界图边数的下界

本文给出了８－临界图边数的下界。     

围长为r的圈布图最大边数的新下界

降为n的图G的圈长分布为序列{C1,C2…,Cn},其中Ci是G中长为i的圈的数目,若图G的圈长分布满足C1＝C2＝…＝Cr-2＝0,Cr＝1,且对i＝r 1,…,n,有Ci≤1,则称图G是围长为r的圈分布图,用fr(n)表示阶为n的围长为r的圈分布图最大可能的边数,本文证明：对每个整数n≥R0（其中：r＝3时,R0=17,r≥4时,R＝3r-[r/2] 5,有fr(n)≥n-r ek t 4 η。     

Ramsey数r(3,10)的下界

以 Kn( p,q)表示红蓝边染色的 n阶完全图 ,图中既无 p个顶点的红边完全子图 ,也无 q个顶点的蓝边完全子图 .本文给出了 K4 0 ( 3,1 0 )的一种构造 ,以改进 Ram sey数 r( 3,1 0 )≥ 4 0的下界     

X-最长圈的下界估计

设Ｇ是连通图,Ｘ＝Ｖ（Ｇ）,Ｇ〔Ｘ〕是Ｇ的Ｘ生成子图,记σｋ（Ｘ）＝ｍｉｎ｛Σｉ＝１ ｋ ｄ（Ｖｉ）;｛ｖ１,ｖ２,…,ｖｋ｝是Ｇ〔Ｘ〕的顶点独立集｝,得到如下结果,对于ｎ阶的１－坚韧图（ｎ≥３）,Ｘ＝Ｖ（Ｇ）,且σ３（Ｘ）≥ｎ＋ｒ≥ｎ,３│Ｘ│－２ｎ≥８ｔ－６ｒ－１７,则存在一个圈Ｃ满足│Ｃ（Ｘ）│≥｛Ｃ（Ｘ）│≥｛│Ｘ│,│Ｎ（Ｉｔ）∩Ｖ（Ｃ）│｝,其中Ｉｔ是Ｘ中ｔ个顶点的独立集。     

收缩临界5连通图中平凡不可收缩边的新下界

证明n个顶点的收缩临界5连通图中至少有n 1条平凡不可收缩边.     

关于Ramsey数下界的一个证明思路

已知图K3的4色Ramsey数的上下界是51≤r4（3）≤62,利用“无和集”划分,提出改进其下界的一个证明思路。