关于简单的MCD图边数的下界

简单的MCD图是指有n个顶点、任何两个圈的长度均不相等且有最大可能边数的简单图,文献[1]中对简单的MCD图的边数f(n)的下界得出     

简单MCD图的边数的上界

用f(n)(f~*(n))表示具有n个顶点的没有两个等长圈的图(简单图)的最大可能的边数。确定f(n)的问题是Erd(?)s于1975年提出的至今尚未解决的难题。我们称具有n个顶点和f(n)(f~*(n))条边的图(简单图)为MCD图(简单MCD图)。在[2]中,我们已经证明f(n)     

圈长唯一的最大图的边数

Erds于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数。试确定f(n)。 含有f(n)条边、没有两个等长圈的n个顶点的图称为圈长唯一的最大图。     

关于最大唯一圈图

P.Erd(o|¨)s于1975年提出了下列问题:设f(n)是有n个顶点的任何两个圈的长均不相等的图的最大可能的边数,试确定f(n)。十余年来,对这一问题的研究几乎没有进展。我们称Erd(o|¨)s问题中所描述的图为最大     

关于简单MCD图的一个定理

设S_n是n个顶点的没有两个等长圈的简单图的集合。如果对于S_n中的一个图G,S_n中不存在适合|E(G′)|>|E(G)|的图G′,则称其为简单最大圈分布图,简称简单MCD图(ma-     

愉快图的Bodendiek猜想之证明

一个简单图称为愉快的,如果存在用集合S={0,1,2,…,ε}(其中ε=ε(G)是G的边数)中不同整数的顶点标号ι,使得如下定义的诱导边标号ι′对每条边uv都有不同的标号:     

关于竞赛图中王的一些结果

1953年Landau引进了竞赛图中“王”的概念:如果竞赛图T的顶点v能通过长至多为2的有向路到达T的其他各个顶点,则称v 为王.他证明了,竞赛图中出度最大的顶点是王.1980年Maurer 证明了,对于整数n≥k≥1,不存在恰有k 个王和n 个顶点的竞赛图的充要条件是k=2或k=n=4.1982年Bridgland 和Reid 引进了下述概念:设T 是竞赛图,t、c     

图和补图线荫度的关系

定义1对简单图G(V,E),E的分划}普1‘·’‘“,+·““‘,‘”·E一UE,, 讼一t使得E,的导出图G[E;](i一l,2,不含圈的最小n,称为‘的线荫度,。‘(G). 定理1若‘是外平面图,则 a‘(G)成2. 定理2对简单图G(V,E),且下界不可改进.其中P一}V(G).,「x1为不小于x的最小整数.…,,)简记作图和补图线荫度的关系@张忠辅$兰州铁道学院 @王建方$中国科学院应用数学研究所!北京 @徐登洲$西北师范大学~~     

支撑树端点数介值定理的一个简单证明

G.Chartrand在第四届国际图论会议(1980)上提出这样一个问题:若一连通图G分別有含m和n个端点的支撑树,m相似文献   

关于两类图的整和数

本文中的图均指无向简单图,以N,Z分别表示全体自然数及全体整数集合.对子集S(?)Z(N),S上的整和(和)图定义为图G=(S,E),满足条件对u,v∈S,uv∈E当且仅当u v∈s.此时,S称为G的一个整和(和)标号.一个图称为整和(和)图,如果它同构于某一子集S(?)Z(N)上的整和(和)图.容易验证,对一个有m条边的n阶图G,G∪mK_1是一个和图,只需标定G的顶点为2~i,1≤i≤n,同时对v_i,v_j∈E(G),标定对应的孤立点2~i 2~j即可.因此,对每一个图G,存在一个最小的非负整数r,使G∪rK_1为和图,记σ(G)=r,并称为G的和数.图的整和数ξ(G)类似定义,只是标号范围放宽到整数集上.容易看到ξ(G)≤σ(G).     

具有最多边的唯一因子图

§1.引言 设G=(V,E)是简单图,V和E分别是G的顶点集和边集。n=|V|称为顶点数,m=|E|称为边数。设S(?)V,从G中去掉S得到的子图,用G-S表示,就是V-S生成的子图。 G的两条边e_1,e_2若有一个公共端点,称为是关联的.设F(?)E是G的边子集,F中任     

逐点周期映射

设(X,d)为紧致度量空间,f:X→X连续。设f是逐点周期的,如果对每一点x∈X,都存在整数n(x)>0,使f~(n(x))(x)=x,即P(f)=x。设f是周期的,如果存在整数m>0,使f~n=id,即f~n是恒同映射。Montgomery(Amer.J.Math.,59(1937),pp.     

P(n,4)与A(n,4)的简单统一显式

设P(n,k)为整数n分为k部的无序分析的个数,每个分部≥1.这个数已成为组合图论和数论里的重要数据,应用广泛,但却十分难于具体计算.为此,作者已给出P(n,k)的降部恒等式和快速计算的几个定理.但对每一k≥4而言,迄今无法求出简单统一的公式,目前只有 P(n,2)=[n/2]简单统一的公式,目前只有和p(n,3)=.又设A(n,k)为下述Diophantos方程sum from i=1 to k(ix_i)=n (1)的非负整数解的个数.尽管方程(1)看来很特殊,但求A(n,k)也是十分困难的.迄今只有 Hardy给出的 A(n,3)=<(n+3)~2/12>.人们至今无法给出简单统一的 A(n,4).本文所有记号与文献[1,2]相同,表示距实数x的最近整数,并记r=1-(-1)~n/2=0(当n为偶数),1(当n为奇数)(2)本文主要的结果是引理1(转换关系)     

由线性微分算子决定的函数类的极值问题和宽度及其渐近性态

设t_0,…,t_n是n+1个实数,D=(d/dx)。记L_(n+1)(D)=(?)(D-t_i),π(L_(n+1))={S|L_(n+1)(D)S≡0)。(?)_(n+1)表示在任一有限区间上,f~((n))(x)绝对连续,f~((n+1))(x)本性有界函数全体,     

k-full整数的分布

设k≥2是一固定整数。自然数n称为k-full整数,如果对n的所有素因子p,都有p~k|n。我们用A_k(x)表示不超过x的kfull整数的个数。在Lindelf猜想假设下,A. Ivi证明了:     

关于整数集合的加性完备

设B是k个整数组成的集合,N是充分大的整数,假定对每个正整数n≤N,至少存在一个b∈B,使得n=λ~2+b,其中λ为正整数。Erds最早提出了k的下界估计问题,即是否存在c_0>0,使得k≥(1+c_0)N~(1/2),Moser首先定出了c_0=0.06,以后Donagi和Herzog证明了c_0=0.125;Abbott证明了c_0=0.147,他们都假设B为     

关于边不交的Hamiltoh圈

本文所讨论的图均为无向的简单图。用δ(G)表示图G的最小度。一个图G称为Ore-(k)型图,如果任一对不相邻顶点“和v都有d(u)+d(v)≥|V(G)|+k(k为整数)。     

亚纯函数结合于导数的总亏量

一、Drasin的几个问题 设f(z)是开平面上的超越亚纯函数,k为一正整数,f(z)的亏值与亏量是函数值分布论中十分重要与基本的概念,由于这时f~(k)(z)也是超越亚纯函数,于是它也可以有亏值与亏量,那么f(z)的亏值与亏量和f~(k)(z)的亏值与亏量间是否存在什么联系呢?     

经典Ramsey数R(4,12),R(5,11)和R(5,12)的新下界

已知经典Ramsey数R(m,n)(m,n≥2)是一定存在的,但确定经典Ramsey数R(m,n)是组合数学和图论中著名的难题,至今在理论和方法上尚未见到取得突破的迹象,因此近年来各国学者主要用各种方法借助计算机对一些具体的Ramsey数给出估计。王清贤、谢继国等人沿用文献[4]的方法研究一般的循环图,得到一些Ramsey数的下界。这种方法在用字典排列法产生参数时,由于大量同构的图均要一一考察,占用大量计算机机时。因此我们作出新的尝试:利用素数阶循环图的平移和旋转等性质改进了产生参数的方法,提高了运算效率,得到3个Ramsey数的新下界。     

复杂度理论中某些不可证明的真命题

在复杂度理论研究中,上界不断被改进,但下界的研究却迟迟没有重要进展。对于任何一个NP完全性问题,现有最好的算法也需要指数的时间,但数学家们费尽九牛二虎之力也只能证出一个线性时间的下界。这使我们想到:复杂度理论中的许多真命题是不可证明的。但如果只是并行于Gdel的不完全性定理,得出一些诸如:“下界是2。但不可证”的结论,仍不能说明真实下界与理论下界之间的巨大差距。我们得到了下面的结果:定理1设,f(n)≥n是任一时间可构造的函数(例如2~2~m),A是一个可以用谓词P(c)表示“程序c的时间复杂度t(n)不会低于一个常数”的公