Font Size: a A A

Degree Condition And Cycle Containing Linear Forest

Posted on:2010-04-26Degree:MasterType:Thesis
Country:ChinaCandidate:J HeFull Text:PDF
GTID:2120360275979656Subject:Operational Research and Cybernetics
Abstract/Summary:PDF Full Text Request
Given integers k, s, t with 0≤s≤t and k≥0, a (k,t,s) -linear forest F is a graph that is vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order n is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. Aσ2(G) condition that implies a graph G is (k,t)-hamiltionian was proved by Ralph J. Faudree et al. In this paper, we discuss other length cycles of G containing a given (k,t,0) -linear forest, and prove the follow result:Let G be a graph of order n and k, t be positive integers with 2≤k + t≤n, and let F be a (k, t, 0) -linear forest. If(i)σ2(G)≥n + k, when F = Pk+1, and(ii)σ2(G)≥n + k-∈(n,k) otherwise, Then for any r∈[max {4, k + 2t}, n ], G has a cycle of length r or r+1 contain F.
Keywords/Search Tags:cycle, linear forest, degree, pancyclic
PDF Full Text Request
Related items