【作者】 赵友军；

【导师】 李雨生；

【作者基本信息】 同济大学 ， 应用数学， 2007， 硕士

【摘要】 本文对极值图论中的两个问题作了研究，所获得的几个主要结果如下。（1）设br_k(K_t，t)是最小的整数n，使得对K_n，n用k种颜色进行任意着色都会包含一个单色的K_t，t。令z（n；t）表示K_n，n的子图在不包含K_t，t作为其子图的情况下所包含的最大边数。本文将分别证明：当t=2或者t=3时，有br_k(K_t，t)～k^t当k→∞；和z（n；t）～n^2-1／t当n→∞。（2）设图G=（V，E）是一个简单图，如果V的一个点子集V′以及V′中所有的点的邻点覆盖V的所有的点，则称V′是图G的一个控制集。图G中所有的控制集中最少的点数称为图G的控制数，记作β（G）。控制数与独立数有着紧密的联系，图G的最大独立集一定是一个控制集。我们设计了一个算法并应用计算机来实现求出G的一个控制集，因此给出控制数的一个上界。然后，我们可以重复运用在上面的算法得出一个最小的控制集，进而获得图G确切的控制数。这样的算法在Paley图中得到了很好的结果。更多还原

【Abstract】 The main results obtained in this dissertation are as follows.（1） Let br_k(K_{t, t}) be the minimum integer n such that in any edgecoloring of K_{n, n} with k colors there is a monochromatic K_{t, t},and let z（n; t） be the maximum number of edges in a subgraphof K_{n, n} that contains no K_{t, t}. It is shown that for t=2 ort=3, r_k(K_{t, t})～k^t as k→∞, and z（n; t）～n^2-1/t as n→∞,respectively.（2） Let G=（V, E） be a simple graph. A dominating set of a graphG is a set V’（?）V such that V’∪N（V’）=V, where N（V’）=∪_u∈v’N（u）. The domination number of G, denoted byβ（G）,is the smallest cardinality |V’| among all dominating sets of G.Clearlyα（G）≥β（G） since any maximal independent set is adominating set. We design a algorithm to get a dominatingset of graphs, which yields an upper bound for the dominationnumber. By repeated using the algorithm, we can obtain thedomination number of G. The algorithm is effective for Paleygraphs.更多还原