Show simple item record

dc.contributor.authorBilinski, Marken_US
dc.date.accessioned2009-01-22T15:42:13Z
dc.date.available2009-01-22T15:42:13Z
dc.date.issued2008-08-25en_US
dc.identifier.urihttp://hdl.handle.net/1853/26516
dc.description.abstractJackson 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.en_US
dc.publisherGeorgia Institute of Technologyen_US
dc.subjectClaw-freeen_US
dc.subject3-connecteden_US
dc.subjectLong cyclesen_US
dc.subject.lcshGraph theory
dc.subject.lcshDecomposition (Mathematics)
dc.titleApproximating the circumference of 3-connected claw-free graphsen_US
dc.typeDissertationen_US
dc.description.degreePh.D.en_US
dc.contributor.departmentMathematicsen_US
dc.description.advisorCommittee Chair: Yu, Xingxing; Committee Member: Duke, Richard; Committee Member: Tetali, Prasad; Committee Member: Thomas, Robin; Committee Member: Vigoda, Ericen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record