Pancyclicity And Vertex Pancyclicity Of Graphs

The hamiltonian problem named for Sir William Rowan Hamilton can trace its origins to the 1850s. In 1971 Bondy [11] posed that the graph was hamiltonian also implies that it was pancyclic (except for maybe a simple family of exceptional graphs). Many theorems about pancyclicity were given in the following years. Meanwhile, the sufficient conditions even for vertex pancyclicity were examined, since vertex pancyclicity implies pancyclicity and pancyclicity implies hamiltonicity.In [29], the author gave that let G be a 2-connected graph with order n and S(G) ≥ t, if |N(u) ∪ N(v)| ≥ n - t for any nonadjacent vertices u and v in G, then G is pancyclic or n = 2t, G ≌ K_t,t. In this thesis we consider to relax the hypothesis to just think over the vertices with distance 2 and we obtain a sufficient condition for pancyclic graphs. Let G be a 2-connected graph with n vertices, if for any two vertices u, v in G with d(u, v) = 2 we have |N(u)∪N(v)| ≥n -δ, then G is pancyclic or G is isomorphic to one of the followings: (1) G is a 5-cycle, (2) G ≌ K(n/2,n/2).In [3], we have that let G be a graph of order n ≥ 3 such that σ₂ ≥ [4n/3] - 1, then every vertex of G is contained in a 3-cycle. Like the above result, any two vertices which are of distance 2 is discussed, then we obtain the following result in this thesis: let G be a graph of order n ≥ 3 such that d(u) + d(v) ≥ [(4n)/3] - 1 where d(u, v) = 2 in G, then every vertex of G is contained in a 3-cycle.What's more, detailed proofs of the two results are presented. In the last chapter, we give several interesting topics for further work.