| The problem on paths and cycles of graphs is a very important problem in graph theory and the research is also active. Many practical problems can be attributed to the problem of paths and cycles. What is more, the famous Hamilton problem belongs to the problem of paths and cycles of graphs in essence. Many scholars at home and abroad made a lot of research work on this issue.The research results and progress in this area can be found in literature[38]-[42]. The condition of degree and neighborhood unions becomes an important way to study the problems. In this respect, a lot of outstanding achievements have be made. 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 Hamilton path (traceability), longest path, panconnectivity, path extendsibility and so on; the properties of cycle include Hamilton cycle, longest cycle, (vertex-)pancyclicity, vertex-disjoint cycle, cycle extendsibility and so on.However, we can not deny the fact that it is usually very difficult to study Hamilton 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[17]. 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],[19]-[31]. 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, al-most claw-free graphs, (K1,4;2)-graphs etc. In 2005, Liu Chunfang [4] defined a new graph family—[s,t]-graphs, that is, there are at least t edges in every included sub-graphs of s vertices in graph G. According to this graph,Cheng Jianmin defined a new graph family—strong-[s,t] graphs [51], that is, there are at least t independent edges in every included subgraphs of s vertices in graph G. [s,t]-graphs can be used in traffic network, communications, the configuration of computer networks, etc.In this paper, we mainly discuss the properties of graphs' paths and cycles in [s,t]-graphs.In the first chapter, we give a brief introduction about the basic concepts, termi-nologies 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 properties of paths and cycles in [s, t]-graphs and give the following results:Theorem 2.1.6 If G is aδ≥k+l,k-connected [k+l+2,Cl+12+2]-graph (k≥2,l∈N), then G has a Hamilton cycle or G is isomorphic to F (Fig.1)or Kk+l+2 V Gk+l (Gk+l is an arbitrary graph containing k+l vertices).Corollary 2.1.6 If G is aδ≥k+l,k-connected [k+l+2, Cl+12+2]-graph (k≥2,l∈N) with|G|≥2(k+l)+2, then G has a Hamilton cycle.Theorem 2.2.5 If G is aδ≥k+l, fk-connected [k+l+3,Cl+12+2]-graph k≥1,l∈N), then G has a Hamilton path or G is isomorphic to Kk+l+2 VGk+l (Gk+l is an arbitrary graph containing k+l vertices).Corollary 2.2.5 If G is aδ≥k+l, k-connected [k+l+3,Cl+12+2]-graph K≥1,L∈n)with|G|≥2(k+l)+3,then G has a Hamilton path.In the third chapter,we mainly study the pancyclicity of[4,2]-graph and give the following result:Theorem 3.2 If G is connected,almost locally connected[4,2]-graph,then every cycle C of G with 5≤|C|＜|C| is extendable.
|
PDF Full Text Request