不含3正则子图的图的最大可能边数的下界

１９７４年，Ｅｒｄｓ和Ｓａｕｃｅｒ提出如下问题：设ｆ（ｐ）是ｐ个顶点的不含３正则子图的图的最大可能边数，确定ｆ（ｐ）．本文给出：（１）ｆ（ｐ）≥３ｐ－９，ｐ≥４；（２）ｆ（ｐ）≥３ｐ－５，ｐ≥３４．

一类图的边数

设G是具有n个顶点的图，ai是G中长为i的圈的个数，h（n，m，r）为满足对于所有的i，ai≤m且当i＜r时，ai=0的图的最大可能边数。边数为h（n，m，r）并满足对于所有的i，ai≤m且当i＜r时，ai=0的图G全体记为H，本文给出了h（n，m，r）的上、下界并证明当n≥nｏ时，H中的作有图G都不包含n圈。对于Erdos问题，本文绘出了f（n）的新上界。

任何两个圈的长均不相等的图的边数

设 f(n)是有 n 个顶点的任何两个圈的长均不相等的图的最大可能边数。P.Erdos在1975年提出了确定 f(n)的问题(见[1]问题11)。Y.Shi[2]证明了:对于每个 n≥3,f(n)≥n+[((8n-23)^(1/2)+1)/2];作者在[3][4][5]证明了:对于每个 n>((2m+3)/4)e^(2m),f(n)<n-2+(n·1n)(4n/(2m+3))+2n^(1/2)+log_2(n+6);对于每个n≥33,f(n)≥n-1+9[(9+(584n-503)^(1/2)/146],本文证明了:当 t=360q+7(q≥1)时,对于每个 n≥(1381/9)t^2+(26/45)t+(98/45),f(n)≥n+19t-1。

每个圈的长均不相等且不小于r的图的边数

设ｆ（ｎ）是有ｎ个顶点的任何两个圈的长均不相等的图的最大可能边数，Ｐ．Ｅｒｄｏｓ在１９７５年提出的了确定ｆ（ｎ）的问题（见（１）问题１１），设ｆ（ｎ，ｒ）是有ｎ个有顶点的圈长不小于ｒ的任何两个圈的长均不相等的图的最大可能边数，本文给出了ｆ（ｎ，ｒ）的上、下界。