Jackson and Wormald show that every 3-connected K_1,d-free graph, on n vertices, contains a cycle of length at least 1/2 n^g(d) where g(d) = (log_2 6 + 2 log_2 (2d+1))^-1. For d = 3, g(d) ~ 0.122. Improving this bound, we prove that if G is a 3-connected claw-free graph on at least 6 vertices, then there exists a cycle C in G such that |E(C)| is at least c n^g+5, where g = log_3 2 and c > 1/7 is a constant. To do this, we instead prove a stronger theorem that requires the cycle to contain two specified edges. We then use Tutte decomposition to partition the graph and then use the inductive hypothesis of our theorem to find paths or cycles in the different parts of the decomposition.

No description available.

In structural graph theory, connectivity is an important notation with a lot of applications. Tutte, in 1961, showed that a simple graph is 3-connected if and only if it can be generated from a wheel graph by repeatedly adding edges between nonadjacent vertices and applying vertex splitting. In 1971, Halin constructed a class of edge-minimal 3-connected planar graphs, which are a generalization of wheel graphs and later were named “Halin graphs” by Lovasz and Plummer. A Halin graph is obtained from a plane embedding of a tree with no stems having degree 2 by adding a cycle through its leaves in the natural order determined according to the embedding. Since Halin graphs were introduced, many useful properties, such as Hamiltonian, hamiltonian-connected and pancyclic, have been discovered. Hence, it will reveal many properties of a graph if we know the graph contains a spanning Halin subgraph. But unfortunately, until now, there is no positive result showing under which conditions a graph contains a spanning Halin subgraph. In this thesis, we characterize all forbidden pairs implying graphs containing spanning Halin subgraphs. Consequently, we provide a complete proof conjecture of Chen et al. Our proofs are based on Chudnovsky and Seymour’s decomposition theorem of claw-free graphs, which were published recently in a series of papers.