| Graph Theory is a branch of mathematics. Graph theory is also intimately related to many branches of mathematics, including group theory, matrix theory, numerical analysis, probability, topology, and combinatorics. With the development of computer science and mathematics, Graph Theory turns into an important tool to research technology and nature science, even for the social science.Extremal theory is an important part of Graph Theory. The prime example of an extremal problem is the following: given a set of graphsψ={G1, G2,…, Gm}, let ex(n;ψ) denote the greatest size of a graph with order n that contains no subgraph isomorphic to any Gi (1≤i≤m), let EX(n;ψ) denote the set of graphs with order n and maximum size that contains no subgraph isomorphic to any Gi (1≤i≤m).For the extremal problems containing no polygon, forψ={C4}, Clapham investigated the values of ex(n;ψ) (n≤21), Yuansheng investigated the values of ex(n;ψ) (22≤n≤31); Forψ={C3,C4}, Garnick investigated the values of ex(n;ψ) (n≤24); Forψ={C3,C4,C5}, Yuansheng investigated the values of ex(n;ψ) and give the corresponding extremal graphs (n≤42).This paper investigates the values of ex(n;ψ) forψ={C4,C5} andψ={C6}. In this paper, the algorithm of constructing critical graph has been used to construct the critical graphs without C4, C5 and the critical graphs without C6, and the lower bounds of extremal graph have been given, then the upper bounds of the extremal graph can be proved by mathematical induction and contradiction. So is the method of proving the extremal graphs. The main results are:(1) Forψ={C4,C5}, the values of ex(n;ψ) (n≤21) and the corresponding extremal graphs have been given. The mathematical proof has been given as well;(2) Forψ={C6}, the values of ex(n;ψ)(n≤10) and the corresponding extremal graphs have been given. The mathematical proof has been given as well; For 10＜n≤28, the graphs by the different base graphs have been contructed and a good lower bounds have been given.
|
PDF Full Text Request