Properties Of Paths And Cycles In[s,t]-Graphs

Paths and cycles arc two basic structures of graphs, meanwhile, they are also effective tools to analyze graph. The problem on paths and cycles of graphs is a very important problem in graph theory and the research is also active. In fact, Many practical problems can be attributed to the problem of paths and cycles. The properties of path and cycle comes from the hamilton problem, which is the famous topic in graph theory. In this respect, many scholars at home and abroad made a lot of research work on this issue, and a lot of outstanding achievements have be made, can be found in literature[38]-[42]. The research on graphs’ path and cycle is always the active field in graph theory. So far, 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 Hamilton problem in special graphs, such as not containing some forbidden sub-graphs, the one more representative class is claw-free graphs. The first motivation for studying properties of claw-free graphs apparently appeared from Beineke’s char-acterization of line graphs in [18]. In late70s and early80s, the study in claw-free graph becomed to an well-known topic in graph theory, Some famous results about claw-free graphs can be seen in [1]-[3],[19]-[35]. 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, claw-centcr-indcpcndent graph,(K1,4;2)-graphs etc. Some new forbidden subgraphs are also defined continuously.In2005, Liu Chunfang [5] denned a new graph family-[s,t]-graphs, that is, there are at least t edges in every included subgraphs of s vertices in graph G. According to this graph, Cheng Jianmin defined a new graph family strong-[s,t] graphs [52], 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, 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 properties of paths and cycles in strong-[s,t] graphs and give the following results:Theorem2.1.4If G is a κ-connected strong-[κ+3,2] graph with δ≥κ+1, then G has a Hamilton cycle or G is isomorphic to (κ+1)K2∨Gκ(Gκ is an arbitrary graph of order k).Corollary2.1.4If G is a κ-connected strong-[κ+3,2] graph with δ≥κ+1and|G|≥3κ+3, then G has a Hamilton cycle.Theorem2.2.5If G is a κ-connected strong-[κ+4,2]graph with δ≥κ+1, then G has a Hamilton path or G is isomorphic to (κ+2)K2∨Gκ(Gκ is an arbitrary graph of order k).Corollary2.2.5If G is a κ-connccted strong-[κ+4,2] graph with δ≥κ+1and|G|≥3κ+5, then G has a Hamilton path. In the third chapter, we mainly study the Hamilton connectivity of strong-[6,2] graph and give the following result:Theorem3.2If G is a4-connected strong-[6,2] graph with δ≥5, then G is Hamilton connectivity or G is isomorphic to4K2∨G4(G4is an arbitrary graph of order4).In the fourth chapter, we mainly study full cycle1-2extendable of [5,2]-graph and give the following result:Theorem4.2If G is a3-connected, locally connected [5,2]-graph of order n≥8, then G is full cycle1-2extendable.