| Graph theory is a branch of mathematics.The research object is graph.We usually investigate the subgraphs of a graph or the properties of a graph to analyse the structure of a graph.In this thesis,we mainly consider disjoint stars,complete graphs of small order and cycles in graphs and average degree and hamiltonicity of edge critical graphs.A graph G is said to be K1,r-free if G does not contain an induced subgraph isomorphic to K1,r.In particularly,when r = 3,we call such graph a claw-free graph.In 2008,Fujita proposed a conjecture about K1,r-free graphs:Let k,r,t be integers with k≥2,r≥3 and t ≥2.If G is a K1,r-free graph of order n≥(k-1)(t(r-1)+1)+ 1 with δ(G)≥t,then G contains k vertex-disjoint copies of K1,t.Fujita showed that the conjecture is true when t = 2orr = t = 3,and he also showed that the conjecture is true when n ≥(t+1)(k-1)(t(r-1)+1)+1.In Chapter 2,we prove that when r>4,t =3 or r≥2t-1,t≥3 or n≥(k-1)(t(r-1)+ 1 +(t-1)(t-2))+ 1,the conjecture is true.Moreover,we construct a graph G’ of order 10k-10 with S(G’)= 4 such that G’ does not contain k vertex-disjoint copies of K1,4,so the graph G’ is a counterexample of Fujita’s conjecture when r=3 and t = 4.A graph is called complete graph if any two vertices form an edge,and we denote it by Kn if the order of this graph is n.In 1998,Wang proved that if G is a claw-free graph of order at least 3s and σ2(G)≥3s + 1,where s is a positive integer,then except some examples,G contains s vertex-disjoint copies of K3.In Chapter 3,we consider vertex-disjoint K3s and K4s in claw-free graphs,and we prove that for all positive integers s and k and a claw-free graph G of order n,if n ≥3s + 4(k-s)and d(x)+ d(y)≥n-2s + 2k+1 for any pair of non-adjacent vertices x,y of G,then G contains s disjoint K3s and k-s disjoint K4s such that all of them are disjoint.Let k be a positive integer.Let G be a graph of order n ≥ 3 and W a subset of V(G)with |W|>3k.In 2015,Wang considered the partial degree conditions of a graph which contain disjoint special cycles and proved that if d(x)≥2n/3 for each x ∈ W,then G contains k vertex-disjoint cycles such that each of them contains at least three vertices of W.In Chapter 4,we consider an analogue problem in bipartite graph.Let G =(V1,V2;E)be a bipartite graph with |V1|=|V2|=n,and let W be a subset of V1 with|W|≥2k,wherek is a positive integer.We show that if d(x)+ d(y)≥n + k for every pair of non-adjacent vertices x∈W,y∈V2,then G contains k vertex-disjoint cycles such that each of them contains at least two vertices of W.Let G be a graph.An edge-k-coloring of a graph G is a mapping cp:E(G)→{1,2,...,k} such that φ(e)≠φ(f)for any two adjacent edges e and f.We call {1,2,...,k} the color set of φ.Denote by Ck(G)the set of all edge-k-colorings of G.The chromatic index χ’(G)is the least integer k≥0 such that Ck(G)≠ 0.Denote by △ and d(G)the maximum degree and the average degree of G,respectively.A graph G is called edge-△-critical if χ’(G)= △+1 and χ’(H)≤△ for any proper subgraph H of G.In 1968,Vizing proposed an average degree conjecture of edge-chromatic critical graphs,that is,if G is an edge-△-critical graph of order n,then d(G)≥ △-1 + 3/n.Woodall in 2007 proved that if G is an edge-△-critical graph,then d(G)≥2/3(△+ 1).In Chapter 5,we give a new structure of edge-A-critical graph and show that if G is an edge-A-critical graph,then This result improves Woodall’s result for △≥56.Additionally,in 2017,Chen,Chen and Zhao considered the hamiltonicity of edge-A-critical graphs and proved that every edge-chromatic critical graph with maximum degree at least 3|G|/4 is Hamiltonian.We improve this result when n>144 and prove that every edge-chromatic critical graph with maximum degree at least 2|G|/3 + 12 is Hamiltonian. |
PDF Full Text Request