Two Problems In Extremal Graph Theory

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.