On The Parameters And The Existence Of Specified Subgraphs In Graphs

The subgraph existence problem is a hot topic in the research of Graph Theory.It not,only has important theoretical significance,but also enjoys strong applica-bility in theoretical computer science,biological science,management science and information science.In this thesis,we concentrate on the study of the parameter-s and the existence of specified subgraphs in graphs.This thesis consists of four section.In the first section,we give some definitions and notations that we needed in this paper.After that,we introduce the background and significance of the research,including the development at home and abroad regarding this aspect.Based on this research background and profound discussion on the status quo,it fully shows the main work's necessity and innovation.In the second section,we consider the following problem proposed by Locke and Zhang[47]:Let k ? 2 and m>k be integers.Let G be a k-connected graph with minimum degree d.For any set X(?)V(G)of m vertices on a cycle,does G have a cycle C of length at least min{2d,|V(G)|? passing through X?Fujisawa and Yamashita solved this problem for the case k>3 and m = k+1 in[Journal of Graph Theory 58(2008),179-190].We provide an affirmative answer to this problem for the case of ? 3 and k + 1 ?m?[4k+1/3].In the third section,we will do research on l-knitted graph.Let G be a graph and S a subset of V(G).The pair(G,S)is knittedif,for every partition of S into non-empty subsets S1,S2,…,St there exist disjoint connected subgraphs C1,C2,...,Ct in G so that Si(?)C V(Ci)for 1?i?t.A graph G is l-nitted if(G,S)is knitted for all subsets S of V(G)with |S|=l.Firstly,we obtain a sharp degree sum condition for a graph G to be(G,S)-knitted,which involves only the degree sum of nonadjacent vertices of S.Secondly,we show that every 6l-connected graph is l-knitted,which improves an earlier upper bound obtained by Kawarabayashi and Yu[J.Combin.Theory Ser.B 103(2013),320-326].We show that if G is a minimal k-chromatic graph with no Kk minors,then G is[Fk/6]-connected.In the fourth section,we will focus on the saturation number of the linear forests P4 U P3 U tP2.The notion for the saturation number of a graph was introduced by famous graph expert Erdos et al.in[A problem in graph theory,Amer.Math.Monthly 71(1964),1107-1110].In section 4,our main result is as follows:Let n?6t + 22 and t>1 be integers.Then sat(n,P4 ? P3 ? tP2)= 3t + 10.Moreover,G ? SAT(n,P4?P3? tP2)if and only if G? K5 U tK3?(n-3t-5)K1.