Some Properties Of Paths And Cycles In P₃-dominated Graphs

Graph theory is one of the important branches in a modern mathematics, andit become more wildly in many aspects, such as urban planning, information trans-mission, electrical network, and so on. Paths and cycles are two basic structures ofgraphs, meanwhile, they are also efective tools to analyze graph. Many practicalproblems can be attributed to the problem of paths and cycles. The problem onpaths and cycles of graphs is a very important problem in graph theory and theresearch is also active. What is more, the famous Hamilton problem belongs to theproblem of paths and cycles of graphs in essence. Many scholars at home and abroadmade a lot of research work on this issue.The research results and progress in thisarea can be found in literature [28]-[32]. The condition of degree and neighborhoodunions becomes an important way to study the problems. In this respect, a lot ofoutstanding achievements have been made. After the development for dozens ofyears, the contents in properties of graphs’path and cycle become more and morerich and specific. The properties of path include Hamilton path (traceability),longest path, Hamilton connected, panconnectivity, path extendsibility and so on;the properties of cycle include Hamilton cycle, longest cycle,(vertex-)pancyclicity,cycle extendsibility, vertex-disjoint cycle, cycle covering, and so on.However, we can not deny the fact that it is usually very difcult to studyhamilton problem in those graphs without any restriction. Then we turn to explore the graphs not containing some forbidden subgraphs such as claw-free graphs.The first motivation for studying properties of claw-free graphs apparently appeared from Beineke’s characterization of line graphs in[4]. 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. Some famous results about claw-free graphs can be seen in[1]-[3],[10]-[22].In addition,the definition of claw-free graph has been extended to several larger graph families in different views,such as quasi-claw-free graphs,almost claw-free graphs,(K1,4;2)-graphs etc.In 1998,A.Ainouche pose the concept of quasi-claw-free,and we call make many results of claw-free generalize to quasi-claw-free.some famous results about claw-free graphs can be seen in[5],[24]-[26].In 2006,H.J.Broersma and E.Vumar firstly pose the concept of P3-dominated graphs,and they make many results of quasi-claw-free generalize to P3-dominated graphs.In this paper,we mainly discuss the properties of graphs’paths and cycles in P3-dominated 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 the Hamilton cycle of different condi-tions in P3-dominated graphs and give the following results:Theorem 2.1.6 let G be a 2-connected P3-dominated graph of order n(≥3), if 2|N(x)∪N(y)|+d(x)+d(y)≥2n-5,for any pair of mon-adjacent vertices x,y, then G has a Hamilton cycle or G∈{K2,3,K1,1,3}.Corollary 2.1.7 let G be a 2-connected P3-dominated graph of order n(≥3), if |N(x)∪N(y)|≥(2n-5)/3,for any pair of non-adjacent vertices x,y,then G has a Hamilton cycle or G∈{K2,3,K1,1,3}.Theorem 2.2.3 let G∈{K2,3,K1,1,3}be a k-connected(k≥2)P3-dominated graph of order n(≥3). (1)if for any distinct vertices u and v in any independent set S of cardinality k+1,|N(u)∪N(v)|≥(2n-3k+1)/3,then G is Hamiltonian.(2)if for any distinct vertices u and v in any independent set S of cardinality k+1,|N(u)∪N(v)|≥n-k-△s,then G is Hamiltonian.In the third chapter,we mainly study the pancyclicity of P3-dominated graph and give the following result:Theorem 3.2.4 Let G be a 2-connected P3-dominated graph,and does not have deduced subgraph isomophic to K2,3,if every deduced subgraph isomophic to Z2 satis tes the characteristic ofφZ2(a1,b1)andφZ2(a1,b2),then G is pancyclicity.In the fourth chapter,we mainly study the hamilton comected P3-dominated graphs and give the following result:Theorem 4.3 Let G beδ≥4 and a 3-comected P3-dominated graph of order n(≥3),if d(x1)+d(x2)+d(x3)≥n+1,for any three vertices of independent set{x1,x2,x3),then G is Hamilton connected.