On Cycles And Paths Of P₃-dominated Graphs And (K_{1, 4}; 2)-graphs

Cycles and paths are two basic structures of graphs, meanwhile, they are also effective tools to analyze graph. Many practical problems can be attributed to the problem of cycles and paths. The study of properties of cycle and path comes from the hamilton problem.which is the famous topic in graph theory. The research of hamiltonicity has made a great progress.the results and advances in this aspect can be refered to [26]-[29]. The study on graphs cycle and path is always an active field in graph theory. After the development for dozens of years.the contents in properties of graphs cycle and path become more and more rich and specific. The properties of cycle include Hamilton cycle.longest cycle, (vertex-)pancyclicity. vertex-disjoint cycle.completely cycle extendsibility and so on: the properties of path include Hamilton path (traceability). longest path. panconnectivity. path extendsibility and so on. More over. in the part of graphs connectivity some scholars defined many new concepts continuously such as N₂- locally connect. triangularly connect. quadrangularly connect and so on. which provides new thinkings for the study of properties of cycle and path.It is usually very difficult to study properties of cycle and path in those graphs without any restriction. so the work in this aspect is mainly aimed at special graph classes which are the graphs not containing some forbidden subgraphs. The one more representative class is claw-free graph which is the graph with no induced K_1,3. The first motivation for studying properties of claw-free graphs apparently appeared from Beineke's characterization of line graphs in [30]-[31]. However, the main impulse that turned the attention of the graph theory community to the class of claw-free graphs was given in late 70s and early 80s. There has been a lot of results on claw-free graph up to now. In addition. the definition of claw-free graph has been extended to several larger graph families in different views, such as claw-center-independent graph.quasi-claw-free graphs.almost claw-free graphs. (K_1,p;q)-graphs. strongly almost claw-free graphs etc. In recent years, some new graph classes have been defined continuously one of which is P₃-dominated graph. In 2006, H.J.Broersma and E.Vumar gave the conception of the P₃-dominated graph.when they visited Nankai University. And they have obtained a series of results which can be refered to [2]. In this paper. we made a preliminary study on P₃-dominated graphs and obtained a few results. In addition.we studied the vertex-pancyclicity of (K_1,4(?)2)-graphs.In the first chapter, we give a brief introduction about the basic concepts. terminologies and symbols which will be used in this paper. In the meantime.we also give some related research backgrounds and some known results.In the second chapter.we mainly study hamiltonicity of P₃-dominated graphs under two conditions and give the following results:Theorem2.6 Let G is a 2-connected P₃-dominated graph with no induced K_2,3 such that every induced Z₁ of G satisfiesΦ_Z1(a,b₁) orΦ_Z1(a,b₂), then G is hamiltonian.(Z₁ is as in Fig2.1)Theorem2.7 Let G is a 2-connected P₃-dominated graph with no induced K_2,3 such that every induced Z₂ of G satisfiesΦ_Z2(a₁,b₁) andΦ_Z2(a₁,b₂).then G is hamiltonian.(Z₂ is as in Fig2.2)In the third chapter.we mainly study vertex-pancyclicity of (K_1,4(?)2)-graphs and obtain the result as follows:Theorem 3.1 Let G is a connected (K_1,4(?)2)-graph with minimum degree at least four and independent claw-centers such that every induced Z₁ of G satisfiesΦ_Z1(a,b₁) orΦ_Z1(a,b₂). then G is vertex - pancyclic.(Z₁ is as in Fig2.1)In the fourth chapter.we mainly study largest cycles of 2-connected P₃-dominated graphs and give the following result:Theorem 4.5 Let G is a 2-connected P₃-dominated graph on n vertices with no induced K_2,3. then length of the largest cycles of G is at least min{n,2δ+4}.In the last chapter. we give the following results about P₃-dominated graphs:Theorem 5.1.1 Let G is a 2-connected P₃-dominated graph. v∈V(G), and P is the longest path with |V(P)|<|V(G)|. such that if (?)xu∈E(V(G-P).V(P)-{v})(x∈V(G-P).u∈(V(P)-{v})), then u^-u⁺∈E(G). Theorem 5.2.3 Let G is a 3-connected P₃-dominated graph on n vertices. if NC≥(2n-6)/3,then G is homogeneously traceable.Theorem 5.3.2 Let G is a 2-connected P₃-dominated graph on n vertices. if NC≥(2n-3)/3, then G is homogeneously traceable.