Forbidden Subgraph And Properties Of Path And Cycle In Graghs

Path and cycle are two basical structures of graph, meanwhile, they are also effective tools to analyze graph. Many practical problems can be sumed up to the study of path and cycle in graphs. The properties of path and cycle comes from the hamilton problem, which is the famous topic in graph theory.The study of hamiltonicity has made a great progress, the results and advances in this aspect can be refered to [3]-[7]. The research on graphs' path and cycle is always the active field in graph theory. After the development for dozens of years,the contents in properties of graphs' path and cycle become more and more rich and specific. The properties of path include traceability,longest path,panconnectivity ,path extendsibility and so on;the properties of cycle include hamilton cycle,longest cycle, (vertex-)pancyclicity, cycle extendsibility and so on.Because it is difficult to study properties of common graphs, the work in this aspect is mainly aimed at special graph classes. The one more representative class is claw-free graph. The first motivation for studying this graph class appeared from the Beineke's characterization of line graph in [8],[9].In the last 80s and 90s, the study in claw-free graph becomed to an well-known topic in graph theory,up to now, there has been a lot of results on claw-free graph.In addition, many other graph classes, which stemed from claw-free graph, for example almost claw-free graph, claw-center-independent graph,quasi-claw-free graph,(K_1,p;q)—graph has been studied.These graph classes are either the extension of claw-free graph or related to claw-free graph closely. Some new forbidden subgraphs are also defined continuously. In this paper, we mainly study some forbidden subgraphs and properties of path and cycle.In the first chapter ,we will introduce the background and some conclusions, as well as the basic concepts, terminologies and symbols involved in the paper.In the second chapter,we mainly study the traceability of quasi-claw-free graphs. This chapter is divided into four sections, first we introduce the concept of quasi-claw-free graph, then we prove the following main theorems mainly.Lemma 2.2.1 Let G be a connected quasi-claw-free graph of order n, P is a path of length r(3 < r < n), if there isn't a path of length r + 1 in the G, then u^u+ G E{G) for all ux G E(V(P), V(G) - V(P)).Lemma 2.2.2 Let G be a connected quasi-claw-free graph of order n, P is a longest path of G(\P\ < n), H is a connected branch of G - P,ux,vy G E{V(P),V(H))(u,v G V(P);x,yï¿¡V(H)),then(a) u 0 {v^,v²,v³,v+,v+2,v+3}(b) v-,v+,v²,v+2 <ï¿¡N{u)(c) E({u-, u-2}, {?", v-2}) = 0 = E({u+, u+2}, {?+, v+2}).Theorem 2.2.3 Let G be a 2-connected quasi-claw-free graph with \G\ — n, if NC > ^,then G is traceable.Lemma 2.3.1 Let G be a connected quasi-claw-free graph, v ï¿¡ V(G), P is a longest z;-path of G, ux e E(V(P) - {v},V(G - P))(u € V(P),x e V(G - P)),then u'u+ e E(G).Theorem 2.3.2 Let G be a 3-connected quasi-claw-free graph with |G| = n, if NC > ^y^,then G is homogeneously traceable.Theorem 2.4 Let G be a 2-connected quasi-claw-free graph with |G| = n, if NC > 2jY^,ihen G is homogeneously traceable.In the third chapter,we will study the path properties of (KiiP;^)-graph(p=4,q=l,2). This chapter is divided into three sections, we introduce the concept of (KitP;q)— graph in the first section, we study the 3-walk about {K\^\ 1)—graph in the second section and the path extendsibility about (if 1,4;2)-graph in the third section. The main theorems in this section are as follows:Lemma 3.2.1 Let G be a K\^ — free graph, x G V(G), and C is a covering walk. If v(x, C) > 4, then there exists a covering walk C such that l(C) < 1{C) - l,V{x, C) = V(x, C) - 1 and v(y, C) < V(y, C) for all y G V(G)(y # x).Corollary 3.2.2 The shortest covering walk of every connected KXii - free graph is a 3-walk.Corollary 3.2.3 Every connected K\A — free graph has a 3-walk.Corollary 3.2.4 In a connected A'14 — free graph, if there is a covering walk visiting the vertex x exactly n(n < 3) times, then there is a 3-walk visiting x exactly n times.Claim 3.2.5 Let G be a connected K\^ — free graph and x 6 V(G), then there is a 3-walk C such that v(x,C) = 1 if and only if x is not a cutvertex of G.From the Corollary 3.2.3 and the Claim 3.2.5 we can gain:Theorem 3.2.6 There is a 3-walk in every connected K^^ — free graph, and for x ï¿¡ V(G) there exists a 3-walk visiting x exactly once if and only if x is not a cutvertex of (?.Theorem 3.3.4 If G is a connected, locally 2-connected (if^;2)—graph with jG| > 7 and 8 > 3, then G is path extendable.In the fourth chapter,we study the cycle properties of claw-center-independent graph and T3 — confined graph. These two kinds of graphs are all related with claw-free graph closely, while T3 — confined graph is an new graph class defined in this paper. In the first section, we mainly study pancyclicity mod k of claw-center-independent graph, in the second section we study the hamiltonicity of T3 — confined graph. The main theorems are as follows:Theorem 4.1.4 Let G is a 2-connected claw-center-independent graph, every non-claw-center vertex v satisfies d(v) > k + 1, for every claw-center vertex u there exists v ï¿¡ N(u) such that d(v) > k + 2, then G is vertex-pancylic mod k.Theorem 4.2.1 G is 2-connected non-hamilton T3 — confined graph if and only if G ï¿¡ F' = {Kt V H : H is the supporting subgraph of Km,2 |,then G is hamiltonion.