4-cycles In Graphs And Related Problems

In this thesis,we investigate extremal problems for supersaturated graphs,and the independence number and nonseparating independence number in a graph.First of all,we count the number of 4-cycles and complete bipartite graphs K2,t+1 in a graph,respectively.Secondly,we obtain the lower bound and upper bound of independence number for a cubic graph by means of maximum induced forests(or decycling sets).What’s more,using the graph embedding,we present two formulae to the nonseparating independence number of a graph.In Chapter 1,we introduce some essential definitions and useful notations,and give main results in this thesis.In Chapter 2,we study the extremal problems of supersaturated graphs.Erd?s and Simonovits[20]conjectured that an n-vertex graph G with ex(n;C4)+1 edges may contain at least(?)4-cycles.Firstly,we show the following results:(1)The number of 4-cycles in an n-vertex graph G with(?)(?)is at least where ?>0.(2)If n is large enough,then there are at least 4-cycles in an n-vertex graph with(?)edges which has k vertices whose degrees are mutually different,where ?>0,and(?)(?).(3)An n-vertex graph G contains at least copies of K2,t+1 provided that(?),where ?>0.Then,we obtain a formula to the number of 4-cycles and K2,t+1 in a graph,respectively,and give their applications.In Chapter 3,we study the lower and upper bounds of independence number of cubic graphs.We prove that the independence number α(G)of an n-vertex cubic graph satisfies where m(S)=|E(S)|+c-1 is the margin number of a minimum decycling set S in which |E(S)| and c are,respectively,the number of edges of G[S]and the number of components of G-S.For a cubic graph G of order n,we show that if and only if every largest induced forest in G contains two disjoint independent sets Ir and Ib of G such that |Ir|=α(G)and |Ir|-|Ib|≤1.Many examples illustrate that the above lower bound may be sharp.This result permits cubic graphs containing triangles which are excluded by several more results of Staton[59]and Heckman[37].Furthermore,we study the independence number of Fullerene graphs Fm,a type of 3-connected cubic triangle-free planar graphs.In Chapter 4,we investigate the nonseparating independence number of a graph G.For a graph G,we show that the nonseparating independence number of G is Z(G)=max{α1(T)|T is a spanning tree of G},where α1(T)is the independence number of subgraph induced by all leaves of a spanning tree T in G.Applying the formula,we obtain the nonseparating independence number of Halin graphs and circular graphs,respectively.Also,we get another method to determine the nonseparating independence number of a graph G by means of large genus embedding of G.Namely,in which S is a nonseparating independent set(not necessarily maximum),γM(G)is the maximum genus and ξ(G)is the Betti deficiency in a graph G.By this formula,we arrive at the nonseparating independence number of the k-cube,cubic graphs and subcubic graphs,respectively.In Chapter 5,we give some related problems of independence number and supersaturated graphs for further research.