论文部分内容阅读
本论文研究了两个问题,共分为三章内容。
第一章我们首先对本论文中经常使用的符号和概念加以定义,然后分别对所研究问题的背景、进展以及我们得到的结果作一个综述。
在第二章我们研究了和图中长度为3的路的计数有关的Nordhaus-Gaddum型极值问题。令H是一个固定的图,对正整数l,记N(l,H)为l条边的图中含有的同构于H的子图的最大数目。作为对Erd(o)s所提的一个问题的回答,对任何图H,Alon([3])确定了N(l,H)的阶(在相差一个常数系数的意义下)。进一步,Bollobás和Sarkar([16])研究了H为Ps,即长度为s的路的情况下N(l,H)的性质,决定了l趋于+∞意义下的渐近最优估计。受Bollobás和Sarkar对s=3即N(l,P3)的研究的启发,我们考虑了如下Nordhaus-Gaddum型极值问题,即研究q3(n)=min{p3(G)+p3((-G))∶|V(G)|=n}的性质,这里p3(G)表示图G中长度为3的路的数目。对所有n≥5,我们精确地决定了p3(G)+p3((-G))的下界,即有:(1)q3(n)=n/8(n-3)(n2-5n+8),n≡0(mod4);(2)q3(n)=n/8(n-1)(n2-7n+14),n≡1(mod4);(3)q3(n)=n-2/8(n3-6n2+11n-2),n≡2(mod4);(4)q3(n)=n+1/8(n-3)(n2-6n+12),n≡3(mod4).
在第三章中,我们研究了有向图的反奇异标号的一些问题。对有向图G=(V,E),其中|E|=m,的一个反奇异标号指的是从G的边集E到{1,2,…,m}的一个一一映射(相当于给G的每条边一个标号),使得G的各个顶点处的有向和两两互不相等,这里顶点x∈V处的有向和指的是指向x的有向边获得的标号之和减去从x出发的有向边获得的标号之和的差。我们证明了:
(a)存在一个绝对常数C>0,对每个具有n个顶点的有向图G,如果G满足min{δ+,δ-}≥C logn,则G有一个反奇异的标号;
(b)对每个完全多部图的边进行完全双定向而得到的有向图有一个反奇异的标号。
第三章的第五节中我们对Stewart([52])定义的图的奇异标号和素奇异标号作了一些简要的讨论。注意到Ben Green和Terence Tao的工作([34])(此项工作在Fefferman为TerenceTao致的Fields奖之获奖词中被提及):对任意正整数k,素数列里存在长为k的恰为等差数列的子列,我们得到:
(c)每个奇异的正则图都是素奇异的。这个事实肯定地解决了Stewart的相应的猜想。